🎯 问题分析
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,5,7,101] 或 [2,5,7,18]
🔑 动态规划思路
-
定义状态：
dp[i]表示以nums[i]结尾的最长递增子序列的长度（你完全正确！👏） -
初始化：
每个元素本身至少可以形成一个长度为1的子序列，所以dp[i] = 1（初始值） -
状态转移方程：
对于每个i，向前找所有j < i且nums[j] < nums[i]的情况：
dp[i] = max(dp[i], dp[j] + 1) -
最终结果：
取dp数组中的最大值（因为最长子序列可能以任意元素结尾）
💻 C++ 代码实现
#include <iostream>
#include <vector>
#include <algorithm> // 使用max_element
using namespace std;
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
vector<int> dp(n, 1); // 初始化所有dp[i]=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);
}
}
}
// 返回dp数组中的最大值
return *max_element(dp.begin(), dp.end());
}
int main() {
vector<int> nums = {10,9,2,5,3,7,101,18};
cout << lengthOfLIS(nums); // 输出4
return 0;
}
🧠 逐步模拟（以示例输入为例）
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| nums | 10 | 9 | 2 | 5 | 3 | 7 | 101 | 18 |
| dp | 1 | 2 | 3 | 4 | ||||
- i=3（nums[3]=5）：
检查 j=0→10>5（跳过），j=2→2<5 → dp[3]=dp[2]+1=2 - i=5（nums[5]=7）：
能找到 j=2(2<7→dp=1+1=2), j=3(5<7→2+1=3), j=4(3<7→2+1=3) → dp[5]=3 - i=6（nums[6]=101）：
前面所有比它小的元素中，最大的dp是dp[5]=3 → dp[6]=4
🚀 时间复杂度优化提示
当前代码是 O(n²)，适合n较小时。如果n很大（比如1e4以上），可以用「贪心+二分查找」优化到 O(n logn)。想了解优化方法吗？可以告诉我哦！( •̀ ω •́ )✧
小练习：尝试手动计算 nums = [3,4,-1,0,6,2,3] 的dp数组，答案应该是4（序列是[-1,0,2,3] 或 [3,4,6,3]？哦不，第二个不递增，仔细想想~）
1 条评论
-
bitworld 最强壮的男人 SU @ 2025-2-16 16:58:49用「贪心+二分查找」将时间复杂度优化到 O(n logn)，并且只用基础数组实现。先看核心思想：
🌟 优化思路
想象你在叠罗汉，要叠得尽可能高，规则是：
- 如果当前人比最上面的高，直接叠上去
- 否则，找到下面第一个可以被他替换的人（保持整体尽可能矮，方便后面叠更高的人）
这就像维护一个「最小尾部序列」，使得每个位置的值都是当前能找到的最小可能值。
📝 代码实现（纯数组版）
#include <iostream> using namespace std; // 辅助函数：二分查找第一个≥target的位置 int binary_search(int arr[], int len, int target) { int left = 0, right = len; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < target) { left = mid + 1; } else { right = mid; } } return left; // 返回插入位置 } int lengthOfLIS(int nums[], int n) { if (n == 0) return 0; int tails[1000]; // 假设n不超过1000 int len = 0; // 当前tails的有效长度 tails[len++] = nums[0]; // 初始化第一个元素 for (int i = 1; i < n; i++) { if (nums[i] > tails[len-1]) { tails[len++] = nums[i]; // 直接追加 } else { // 找到第一个≥nums[i]的位置替换 int pos = binary_search(tails, len, nums[i]); tails[pos] = nums[i]; } } return len; } int main() { int nums[] = {10,9,2,5,3,7,101,18}; int n = sizeof(nums)/sizeof(nums[0]); cout << lengthOfLIS(nums, n); // 输出4 return 0; }
🧠 关键步骤解析
以输入
nums = [3,4,-1,0,6,2,3]为例：步骤 当前数 tails数组变化 len 1 3 [3] 1 2 4 [3,4] 2 3 -1 [-1,4] 4 0 [-1,0] 5 6 [-1,0,6] 3 6 2 [-1,0,2] 7 3 [-1,0,2,3] 4 最终结果长度是4（实际序列可能是
[-1,0,6,3]不对，但长度正确，这里重点在长度计算）
🔍 为什么能保证正确性？
- 贪心策略：每次替换保持尾部尽可能小，给后续更大的数留空间
- 数学证明：tails数组的长度就是LIS的长度（可用归纳法证明）
✨ 复杂度对比
方法 时间复杂度 空间复杂度 基础DP O(n²) O(n) 贪心+二分查找 O(n logn)
小挑战：尝试修改代码处理输入
nums = [4,10,4,3,8,9]，正确答案是3（比如[4,4,8]不算递增，实际最长是[4,10]或[3,8,9]长度3）
- 1