牛客网4456题 最长递增子序列：动态规划+二分查找

一、C++代码实现

class AscentSequence {
  public:
    int findLongest(vector<int> A, int n) {
        vector<int> dp; // 维护一个递增序列
        for (int num : A) {
            // 使用lower_bound找到第一个不小于当前元素的位置
            auto it = lower_bound(dp.begin(), dp.end(), num);
            if (it == dp.end()) {
                dp.push_back(num); // 当前元素最大，扩展序列
            } else {
                *it = num; // 替换第一个不小于当前元素的值
            }
        }
        return dp.size(); // 最终序列长度即为LIS长度
    }
};

二、原理解析

1. 传统动态规划的局限

常规O(n²)解法使用dp数组记录以每个元素结尾的LIS长度，需要双重循环比较所有前驱元素。

2. 优化思路突破

我们维护一个动态数组dp，其核心特性：

• 始终保持升序排列

• 存储的是当前长度下最小的末尾元素

• 使用二分查找确定插入位置

3. 关键步骤拆解

以输入[2,1,4,3,1,5,6]为例：

1. 初始dp = []

2. 处理2 → dp = [2]

3. 处理1 → 替换2 → dp = [1]

4. 处理4 → 追加 → dp = [1,4]

5. 处理3 → 替换4 → dp = [1,3]

6. 处理1 → 无变化 → dp = [1,3]

7. 处理5 → 追加 → dp = [1,3,5]

8. 处理6 → 追加 → dp = [1,3,5,6]

4. 为什么能保证正确性？

• 替换操作不影响已有序列长度

• 较小的末尾元素为后续增长提供更多可能

• 最终序列不一定是最真实的LIS，但长度绝对正确

三、常见误区警示

1. 错误认为dp存储的就是真实LIS

2. 忽略二分查找必须用lower_bound

3. 未处理空输入的特殊情况