最长上升子序列（LIS）CSP-S

💡 核心思想

最长上升子序列（LIS）是找出序列中最长的严格递增子序列。经典解法是 O(n²) 的 DP：dp[i] 表示以 a[i] 结尾的最长上升子序列长度。进阶解法是 O(n log n) 的贪心+二分：维护一个数组 d，d[len] 表示长度为 len 的上升子序列的最小末尾元素，用 lower_bound 更新。

🎯 直觉理解

想象你正在整理一摞书，要求书的高度严格递增。你可以一本一本往书架上放：新书如果比最后一本高，就直接放上去；如果比最后一本矮，就替换掉书架上第一本比它高的书（这样能让序列更有"潜力"变长）。最终书架上的书数量就是 LIS 长度。

📝 算法流程

1. O(n²) DP：初始化 dp[i] = 1
2. 对于每个 i，遍历 j < i：如果 a[j] < a[i]，则 dp[i] = max(dp[i], dp[j] + 1)
3. 答案为所有 dp[i] 的最大值
4. O(n log n) 优化：维护数组 d，d[len] 表示长度为 len 的 LIS 的最小末尾
5. 对于每个 a[i]，在 d 中用 lower_bound 找到第一个 >= a[i] 的位置，替换为 a[i]
6. d 的有效长度就是 LIS 长度

$$dp[i] = max_{j < i, a[j] < a[i]} {dp[j] + 1}, quad \text{初始 } dp[i] = 1$$

$$O(n log n)\text{：}d[len] = min{\text{长度为 }len\text{ 的 LIS 的最小末尾}}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

// 1. O(n^2) DP
int lisDP(vector& a) {
    int n = a.size();
    vector dp(n, 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
    return *max_element(dp.begin(), dp.end());
}

// 2. O(n log n) 贪心 + 二分
int lisNlogN(vector& a) {
    vector d;
    for (int x : a) {
        auto it = lower_bound(d.begin(), d.end(), x);
        if (it == d.end()) d.push_back(x);
        else *it = x;
    }
    return d.size();
}

// 3. 输出具体方案（记录前驱）
vector lisPath(vector& a) {
    int n = a.size();
    vector dp(n, 1), pre(n, -1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                pre[i] = j;
            }
    int pos = max_element(dp.begin(), dp.end()) - dp.begin();
    vector path;
    for (; pos != -1; pos = pre[pos]) path.push_back(a[pos]);
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    vector a = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << lisDP(a) << endl;      // 4
    cout << lisNlogN(a) << endl;   // 4
    auto path = lisPath(a);
    for (int x : path) cout << x << " "; // 2 3 7 18
    cout << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目