因为只有定义 dp[i] 为“以 nums[i] 结尾的最长递增子序列长度”，才能通过比较 nums[j] < nums[i]（j < i）来转移状态 dp[i] = max(dp[j] + 1)，否则无法保证衔接性。
为什么 dp[i] 定义成“以 nums[i] 结尾的最长递增子序列长度”才对
很多初学者会误把 dp[i] 理解为“前 i 个元素中的 LIS 长度”，但这会导致状态无法转移：你没法从 dp[i-1] 推出 dp[i]，因为新增的 nums[i] 可能接不上前面任何子序列的末尾。只有定义成“以 nums[i] 结尾”，才能明确判断：对所有 j 且 <code>nums[j] ，尝试用 <code>dp[j] + 1 更新 dp[i]。
这个定义让状态转移有依据，也保证每个 dp[i] 是可计算、可验证的局部最优。
标准 O(n²) 动态规划写法要注意什么
核心是两层循环 + 条件更新。容易漏掉的点：
-
dp数组必须初始化为1（每个元素自身构成长度为 1 的递增子序列） - 内层循环
j必须从0到i-1，不能只看前一个 - 更新条件严格是
nums[j] ，不是 <code> - 最终答案不是
dp[n-1]，而是整个dp数组的最大值
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
int n = nums.size();
vector<int> dp(n, 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);
}
}
}
int ans = *max_element(dp.begin(), dp.end()); // ans = 4
想优化到 O(n log n)？必须换思路用贪心 + 二分
O(n²) 在 n > 10⁴ 时可能超时。lower_bound 优化的关键不是加速 DP，而是放弃记录所有可能结尾，转而维护一个数组 tail，其中 tail[len] 表示长度为 len+1 的递增子序列的最小可能末尾值。
立即学习“C++免费学习笔记（深入）”；
这样做的好处：
-
tail始终严格递增 → 支持二分查找 - 每次用
nums[i]替换第一个 ≥ 它的tail[k]，或追加到末尾 - 最终
tail.size()就是 LIS 长度（但tail本身不一定是真实子序列）
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
vector<int> tail;
for (int x : nums) {
auto it = lower_bound(tail.begin(), tail.end(), x);
if (it == tail.end()) {
tail.push_back(x);
} else {
*it = x;
}
}
int ans = tail.size(); // ans = 4
如果需要输出任意一个 LIS，而不是只求长度
O(n²) 方法可以回溯，O(n log n) 方法也可以，但要额外维护两个数组：
-
dp[i]：以i结尾的 LIS 长度（仍需 O(n²) 计算） -
prev[i]：在最优路径中，i的前一个索引（即哪个j贡献了最大dp[j]+1） - 找到
dp最大值对应的位置idx，然后沿prev[idx]回溯构造结果
注意：prev 数组初始化为 -1，回溯时要逆序插入，最后反转才是正序 LIS。
真正难的不是写对算法，而是意识到：O(n log n) 版本天生不保存路径信息；要输出序列，要么接受 O(n²) 时间，要么在贪心版本里同步维护索引映射——后者代码复杂度陡增，实际项目中建议优先确认是否真需要输出子序列本身。
