vvrf / DSA.log

问题拆解

在数组里找最长的严格递增子序列（可以不连续），返回长度。子序列的取舍自由度太大，枚举所有子集是 O(2^n)，不可行。

子序列问题的常见入口是给“结尾”一个名分：定义 dp[i] 为以 nums[i] 结尾的最长递增子序列长度。任何一条递增子序列都被它的结尾唯一归类，答案就是所有 dp[i] 的最大值；而要算 dp[i]，只需枚举它能接在哪个更小的数后面。

状态里带上“以 i 结尾”，转移就变成“上一个元素是谁”——这是子序列 DP 的标准姿势。

以每个位置结尾的 O(n²) DP

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1); // 每个元素自己就是长度 1 的子序列
    int answer = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        answer = Math.max(answer, dp[i]);
    }
    return answer;
}

def lengthOfLIS(nums: list[int]) -> int:
    dp = [1] * len(nums)  # 每个元素自己就是长度 1 的子序列

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

func lengthOfLIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    answer := 0
    for i := 0; i < n; i++ {
        dp[i] = 1 // 每个元素自己就是长度 1 的子序列
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        answer = max(answer, dp[i])
    }
    return answer
}

pub fn length_of_lis(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut dp = vec![1; n]; // 每个元素自己就是长度 1 的子序列
    for i in 1..n {
        for j in 0..i {
            if nums[j] < nums[i] {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
    }
    *dp.iter().max().unwrap()
}

注意答案是 dp 的最大值而不是 dp[n-1]——最长的那条子序列不一定以最后一个元素结尾。两层循环 O(n²)，对 n ≤ 2500 的数据量够用，但题目进阶要求 O(n log n)。

贪心 + 二分：维护 tails 数组

换一个记账方式：tails[k] 表示所有长度为 k + 1 的递增子序列里，结尾最小是多少。直觉是：长度相同时，结尾越小的子序列越有潜力接上后面的数，所以每个长度只需要记住“最好的那个结尾”。

tails 一定是严格递增的（若 tails[k] >= tails[k+1]，把长度 k + 2 那条子序列去掉尾巴就得到一条长度 k + 1、结尾更小的，矛盾）。于是对每个新来的 x，可以二分找到它在 tails 里的位置：

public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int lo = 0, hi = size;
        while (lo < hi) { // 找第一个 >= x 的位置
            int mid = (lo + hi) >>> 1;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = x; // 结尾变小是白赚的改进
        if (lo == size) size++; // x 比所有结尾都大，长度 +1
    }
    return size;
}

import bisect

def lengthOfLIS(nums: list[int]) -> int:
    tails = []
    for x in nums:
        pos = bisect.bisect_left(tails, x)  # 第一个 >= x 的位置
        if pos == len(tails):
            tails.append(x)  # x 比所有结尾都大，长度 +1
        else:
            tails[pos] = x  # 结尾变小是白赚的改进
    return len(tails)

func lengthOfLIS(nums []int) int {
    tails := []int{}
    for _, x := range nums {
        pos, _ := slices.BinarySearch(tails, x) // 第一个 >= x 的位置
        if pos == len(tails) {
            tails = append(tails, x) // x 比所有结尾都大，长度 +1
        } else {
            tails[pos] = x // 结尾变小是白赚的改进
        }
    }
    return len(tails)
}

pub fn length_of_lis(nums: Vec<i32>) -> i32 {
    let mut tails: Vec<i32> = Vec::new();
    for x in nums {
        let pos = tails.partition_point(|&t| t < x); // 第一个 >= x 的位置
        if pos == tails.len() {
            tails.push(x); // x 比所有结尾都大，长度 +1
        } else {
            tails[pos] = x; // 结尾变小是白赚的改进
        }
    }
    tails.len() as i32
}

替换为什么合法？把 tails[pos] 换成更小的 x，并没有破坏“存在长度为 pos + 1、以 x 结尾的递增子序列”这个事实——x 接在 tails[pos - 1] 后面正好是一条。替换只会让后续元素更容易接长，不会虚报长度。两个易错点：必须用 bisect_left（找第一个 >=），若用 bisect_right 会让相等元素接在自己后面，错把非严格递增算进来；另外 tails 本身通常不是一条真实的 LIS，只有长度可信，别拿它当答案序列输出。

复杂度

指标	复杂度	原因
时间	`O(n²)` / `O(n log n)`	DP 两层循环；贪心版每个元素做一次二分
空间	`O(n)`	dp 数组或 tails 数组

可以迁移的模式

子序列 DP 先试“以 i 结尾”做状态，转移枚举前驱；
当状态只用来比较“谁更有潜力”时，同类状态只留最优代表（这里是最小结尾），常能砍掉一维；
bisect_left 对应严格递增，bisect_right 对应允许相等，边界选错答案就错。

“记录每个长度的最小结尾”这套 tails 思路，在俄罗斯套娃信封（354）等二维版本里会原样复用。