【动态规划 -12】300.最长递增子序列

题目描述：

给你一个整数数组nums，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列（子序列是可以通过从另一个数组删除或不删除某些元素，但不更改其余元素的顺序得到的数组）。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]输出：1

解题思路：

方法一：动态规划（O(n²)）

核心思路：

状态定义：

dp[i]= 以nums[i]结尾的最长递增子序列的长度。

状态转移：

对于每个i，枚举j < i：

• 如果nums[j] < nums[i]，说明nums[i]可以接在nums[j]后面

• dp[i] = max(dp[i], dp[j] + 1)

初始化：

dp[i] = 1（每个元素自身就是一个长度为 1 的递增子序列）

具体过程示例：

nums = [10, 9, 2, 5, 3, 7, 101, 18]

最长长度 = 4✅

代码实现：

class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); int result = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } result = max(result, dp[i]); } return result; } };

复杂度分析：

方法二：贪心 + 二分查找（O(n log n)，最优）

核心思路：

维护一个数组tails：

• tails[i]= 长度为i+1的递增子序列的最小结尾元素

• tails是严格递增的

遍历nums，对于每个num：

• 如果num > tails的最后一个元素，直接追加

• 否则，用二分查找找到tails中第一个 ≥ num的位置，替换它

最终tails的长度就是最长递增子序列的长度。

具体过程示例：

nums = [10, 9, 2, 5, 3, 7, 101, 18]

tails 长度 = 4✅

代码实现：

class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int> tails; for (int num : nums) { auto it = lower_bound(tails.begin(), tails.end(), num); if (it == tails.end()) { tails.push_back(num); // 比所有元素都大，追加 } else { *it = num; // 替换第一个 ≥ num 的元素 } } return tails.size(); } };

手动实现二分：

class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int> tails; for (int num : nums) { int left = 0, right = tails.size(); // 找第一个 >= num 的位置 while (left < right) { int mid = left + (right - left) / 2; if (tails[mid] < num) { left = mid + 1; } else { right = mid; } } if (left == tails.size()) { tails.push_back(num); } else { tails[left] = num; } } return tails.size(); } };

复杂度分析：

关键细节：

1. 为什么tails是严格递增的？

因为tails[i]表示长度为i+1的递增子序列的最小结尾，长度越长，结尾一定越大。

2. 为什么用lower_bound而不是upper_bound？

因为要求严格递增，所以要找第一个≥ num的位置替换。

• 严格递增：lower_bound（第一个 ≥ num）

• 非严格递增：upper_bound（第一个 > num）

3.tails为什么不是最长递增子序列？

tails只是维护了每个长度的最小结尾，替换操作会破坏原始顺序。

例子：nums = [1, 3, 2]

tails 变化: [1] → [1,3] → [1,2] 最终 tails = [1,2]，但最长递增子序列是 [1,3] 或 [1,2]

4. 和「最长递增子序列的个数」的区别

两种方法对比：

注意：tails数组不是最长递增子序列本身，只是用于计算长度。

总结：