解题思路

在一个数列里找一个最长的子序列，要求里面的数一个比一个严格大，问最长能有多长。

这道题 N 最大到 100000，如果用朴素的动态规划（每个数往前找所有比它小的数），要 O(n²) 的时间，会超时。所以要用贪心加二分的做法，只要 O(n log n)。

核心想法：维护一个数组 d，其中 d[k] 表示「长度为 k 的上升子序列，末尾那个数能取到的最小值」。

为什么让末尾越小越好？因为末尾越小，后面越容易接上更大的数，越有可能把子序列做得更长。

做法：

1. 从头到尾看每个数 a[i]
2. 在 d 数组里用二分找到第一个不小于 a[i] 的位置 pos
3. 把 d[pos] 替换成更小的 a[i]（这样后面更容易接）
4. 如果 a[i] 比 d 里所有数都大，就追加到末尾，最长长度加 1
5. 最后 d 的长度就是答案

举例：序列 1 3 2 8 5 6

• 遇到 1：d = [1]
• 遇到 3：比 1 大，接上，d = [1, 3]
• 遇到 2：替换掉 3，d = [1, 2]（末尾从 3 变成更小的 2，更容易接）
• 遇到 8：接上，d = [1, 2, 8]
• 遇到 5：替换掉 8，d = [1, 2, 5]
• 遇到 6：接上，d = [1, 2, 5, 6]

最长长度是 4，对应的子序列是 1 2 5 6。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;

int a[100005];  // 原序列
int d[100005];  // d[k] 表示长度为 k 的上升子序列，末尾那个数的最小值

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int len = 0;  // 当前能找到的最长上升子序列长度
    for (int i = 0; i < n; i++) {
        // 在 d 数组里二分查找第一个不小于 a[i] 的位置
        // 这个位置的数可以换成更小的 a[i]，让后面的数更容易接上去
        int pos = lower_bound(d, d + len, a[i]) - d;
        d[pos] = a[i];
        // 如果 a[i] 比所有末尾都大，追加到了末尾，长度加 1
        if (pos == len) {
            len++;
        }
    }

    cout << len;  // 输出最长上升子序列的长度
    return 0;
}

复杂度分析

• 时间复杂度：O(n log n)，每个数二分一次
• 空间复杂度：O(n)，两个数组存原序列和 d