最长递增子序列
进阶LIS 有 O(n²) DP 和 O(n log n) 贪心+二分两种经典解法。
// 算法讲解
最长递增子序列
用贪心+二分法求 LIS 长度。
待机
速度 中
待机 ⌨1int lengthOfLIS(vector<int>& nums) {
2 vector<int> tail;
3 for (int x : nums) {
4 auto it = lower_bound(tail.begin(), tail.end(), x);
5 if (it == tail.end()) tail.push_back(x);
6 else *it = x;
7 }
8 return tail.size();
9}
复杂度分析
时间 O(n log n)
空间 O(n)
最优 O(n)
最坏 O(n log n)
算法讲解
最长递增子序列（LIS）要求在数组中找一个最长的、元素递增的子序列（不要求连续）。
O(n²) DP：dp[i] 表示以 arr[i] 结尾的 LIS 长度，每次向前找所有比 arr[i] 小的位置取 max。
O(n log n) 贪心+二分：维护一个数组 tail，tail[k] 表示长度为 k+1 的递增子序列的最小末尾元素。
LIS 是很多问题的核心子结构，如套娃问题、桥的最多不交叉数等。