Skip to content

1. 连续与非连续先分清 ​

输入为有限数值数组,所有比较严格使用“大于”,不修改输入。连续区间不能跳过元素;子序列可以跳过但不能改变顺序。[1,3,5,4,7] 的最长连续递增长度为 3,最长递增子序列长度为 4。

2. 连续递增:只看前一个位置 ​

处理当前位置时,current 表示以当前位置结尾的连续递增长度;当前值大于前一个值则延长,否则重新开始。全局答案另存,不能把局部状态解释为“到目前为止的最大值”。

js
function findLengthOfLCIS(nums) {
    let current = 0;
    let best = 0;
    for (let i = 0; i < nums.length; i++) {
        current = i > 0 && nums[i] > nums[i - 1] ? current + 1 : 1;
        best = Math.max(best, current);
    }
    return best;
}

空数组返回 0,全相等非空数组返回 1。时间为 O(n),辅助空间为 O(1)。扫描足够时不必建立整张状态表。

3. 非连续递增:考虑所有可接的前驱 ​

定义 length[i] 为以 i 结尾的最长严格递增子序列长度。所有满足 j < i 且 nums[j] < nums[i] 的位置都可能是前驱;每个元素自身至少形成长度为一的序列。

js
function lengthOfLIS(nums) {
    const length = new Array(nums.length).fill(1);
    let best = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) length[i] = Math.max(length[i], length[j] + 1);
        }
        best = Math.max(best, length[i]);
    }
    return best;
}

时间为 O(n²),辅助空间为 O(n)。先掌握状态,再选学二分维护最小结尾的 O(n log n) 方法;那份最小结尾数组本身不一定是一条真实子序列。

4. 最长方案有多少条 ​

再定义 count[i] 为以 i 结尾且达到 length[i] 的方案数。发现更长的候选时替换计数;发现同样长的候选时累加;更短的候选不贡献。

js
function findNumberOfLIS(nums) {
    const length = new Array(nums.length).fill(1);
    const count = new Array(nums.length).fill(1);
    let best = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] >= nums[i]) continue;
            if (length[j] + 1 > length[i]) {
                length[i] = length[j] + 1;
                count[i] = count[j];
            } else if (length[j] + 1 === length[i]) count[i] += count[j];
        }
        best = Math.max(best, length[i]);
    }
    let total = 0;
    for (let i = 0; i < nums.length; i++) {
        if (length[i] === best) total += count[i];
    }
    return total;
}

按下标选择不同算不同方案,故 [2,2,2] 的答案为 3,不是 1;空数组约定返回 0。输入规模须保证计数在安全整数范围内。时间为 O(n²),辅助空间为 O(n)。

5. 验证与复盘 ​

运行 node --test tests/algorithm-strategies-examples.test.mjs。用空数组、全等、下降、重复前驱和 [1,3,5,4,7] 核对;小输入枚举所有下标子集可作为计数的独立对照。

闭卷追问:为什么连续版本只看相邻位置,而非连续版本要看所有前驱?为什么找到更长序列时必须覆盖旧计数?动态规划原理见主文。

评论

正在加载评论…