题目 2668: 蓝桥杯2022年第十三届省赛真题-最长不下降子序列

原题链接：

题目 2668: 蓝桥杯2022年第十三届省赛真题-最长不下降子序列

https://www.dotcpp.com/oj/problem2668.html

完成情况：

解题思路：

代码解释

该代码旨在解决如何通过修改一个整数序列的连续 K 个数，使得修改后的序列的最长不下降子序列（LNDS）的长度最大的问题。以下是代码的详细解释：

主函数 main

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();  // 序列的长度
    int K = scanner.nextInt();  // 需要修改的连续子序列的长度
    int arrA[] = new int[N];    // 输入的整数序列

    for (int i = 0; i < N; i++) {
        arrA[i] = scanner.nextInt();
    }
    scanner.close();

    // 计算初始序列的最长不下降子序列长度
    int initLNDS = computeLNDS(arrA);
    int maxLNDS = initLNDS;

    // 遍历所有可能的连续子序列，尝试将其修改为相同值
    for (int i = 0; i <= N - K; i++) {
        int[] original = Arrays.copyOfRange(arrA, i, i + K);  // 保存原始子序列
        int uniqueVals[] = Arrays.stream(arrA).distinct().toArray();  // 获取序列中所有不同的值

        for (int value : uniqueVals) {
            // 将连续的 K 个数修改为当前值
            for (int j = i; j < i + K; j++) {
                arrA[j] = value;
            }

            // 计算修改后的序列的LNDS长度
            int modifiedLNDS = computeLNDS(arrA);
            maxLNDS = Math.max(maxLNDS, modifiedLNDS);
        }

        // 恢复原始子序列
        System.arraycopy(original, 0, arrA, i, K);
    }

    // 输出最长的LNDS长度
    System.out.println(maxLNDS);
}

辅助函数 computeLNDS

private static int computeLNDS(int[] array) {
    int[] dp_computeLNDS = new int[array.length];
    int length = 0;

    for (int num : array) {
        int pos = Arrays.binarySearch(dp_computeLNDS, 0, length, num);
        if (pos < 0) {
            pos = -(pos + 1);
        }
        dp_computeLNDS[pos] = num;
        if (pos == length) {
            length++;
        }
    }

    return length;
}

代码说明

1. 输入读取：

   • 使用 Scanner 读取输入的整数序列的长度 N 和需要修改的连续子序列的长度 K。
   • 读取序列 arrA。

2. 初始 LNDS 计算：

   • 通过 computeLNDS 函数计算初始序列的最长不下降子序列长度。

3. 遍历所有可能的修改：

   • 遍历所有可能的长度为 K 的连续子序列。
   • 对于每个子序列，尝试将其修改为序列中每一个不同的值。
   • 对修改后的序列，使用 computeLNDS 重新计算最长不下降子序列的长度。
   • 更新最大长度 maxLNDS。

4. 恢复原始子序列：

   • 每次修改后，使用 System.arraycopy 恢复原始子序列，确保每次修改都是独立的。

5. 输出结果：

   • 最后输出最大长度 maxLNDS。

复杂度分析

• 由于需要遍历所有长度为 K 的子序列，并对每个子序列尝试所有不同的值，算法的时间复杂度较高。
• 计算 LNDS 使用了二分查找，因此 computeLNDS 函数的时间复杂度为 O(N log N)。

优化建议

• 由于可能的输入范围较大（N <= 10^5，A[i] <= 10^6），上述算法在最坏情况下的性能可能不足以处理所有测试用例。
• 可以考虑其他优化策略，例如利用滑动窗口等方法减少重复计算，以提升效率。

参考代码：

package leetcode板块;

import java.util.Arrays;
import java.util.Scanner;

public class _题目2668蓝桥杯2022年第十三届省赛真题_最长不下降子序列 {
    /**
     *
     * @param args
     */
    public static void main(String[] args) {
        // 现在你有一次机会，将其中【连续的 K 个数】 修改成 【任意一个相同值】。
        // 请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。
        // TODO 最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。
        /*
            对于所有评测用例，1 ≤ K ≤ N ≤ 10^5，1 ≤ Ai ≤ 10^6。
         */
        Scanner scanner = new Scanner(System.in);
        //  长度为 N  , 将其中连续的 K 个数修改成任意一个相同值
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        int arrA [] = new int[N];
        for (int i = 0; i<N;i++){
            arrA[i] = scanner.nextInt();
        }
        scanner.close();
        // 重点 ：  LNDS:longest non-decreasing subsequence
        int initLNDS = computeLNDS(arrA);
        int maxLNDS = initLNDS;
        // ----------------------------------------------
        for (int i = 0; i <= N-K;i++){
            int [] original = Arrays.copyOfRange(arrA,i,i+K);
            int uniqueVals [] = Arrays.stream(arrA).distinct().toArray();
            for (int value : uniqueVals){
                for (int j = i;j<i+K;j++){
                    arrA[j] = value;
                }
                int modifiedLNDS = computeLNDS(arrA);
                maxLNDS = Math.max(maxLNDS,modifiedLNDS);
            }
            System.arraycopy(original,0,arrA,i,K);
        }
        System.out.println(maxLNDS);
    }

    /**
     *
     * @param array
     * @return
     */
    private static int computeLNDS(int[] array) {
        int [] dp_computeLNDS = new int[array.length];
        int length = 0;
        for (int num : array){
            int pos = Arrays.binarySearch(dp_computeLNDS,0,length,num);
            if (pos < 0){
                pos = -(pos + 1);
            }
            dp_computeLNDS[pos] = num;
            if (pos == length){
                length++;
            }
        }
        return length;
    }
}

错误经验吸取