因为dp[i]定义为“以nums[i]结尾的最长递增子序列长度”，才能确保状态可转移：j<i时dp[j]可直接用于更新dp[i]，若定义为前i个元素的全局LIS，则末尾不匹配，无法安全转移；初始值为1，需双重循环遍历j∈[0,i−1]且满足nums[j]<nums[i]时更新dp[i]=max(dp[i],dp[j]+1)，最终答案为dp数组最大值。
为什么 dp[i] 定义成“以 nums[i] 结尾的最长递增子序列长度”是关键
因为只有这样，状态才能被后续位置复用：dp[j]（j < i）可直接参与转移，而若定义为“前 i 个元素的 LIS 长度”，就无法保证末尾对齐，没法安全转移。
常见错误是把 dp[i] 当成全局最优，结果在更新时漏掉“必须以当前元素结尾”这一约束，导致转移逻辑错乱。
-
dp[i]初始值设为 1（每个元素自身构成长度为 1 的递增子序列） - 对每个
i，需遍历所有j < i，仅当nums[j] < nums[i]时才考虑dp[j] + 1 - 最终答案不是
dp[n-1]，而是max(dp[0], dp[1], ..., dp[n-1])
如何写出正确且易读的 O(n²) DP 循环
核心是两层嵌套：外层定终点 i，内层找合法前驱 j。顺序不能反，否则 dp[j] 还没算好。
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());
注意：dp[i] 只依赖更小下标的 dp[j]，所以从左到右扫描安全；但若数组为空，要提前判 n == 0，否则 max_element 行为未定义。
立即学习“C++免费学习笔记（深入）”；
为什么 lower_bound 能把时间优化到 O(n log n)
本质是维护一个“可能成为某长度 LIS 结尾的最小值”数组 —— 它天然有序，支持二分。每次用 nums[i] 去替换第一个 ≥ 它的数，等价于“尝试延长某个已有长度的序列，或更新该长度的结尾下界”。
- 不存完整子序列，只存每个长度对应的最小结尾值，数组严格递增
-
lower_bound(tails.begin(), tails.end(), nums[i])找到第一个不能接在nums[i]后面的位置 - 若找到末尾，则 push_back；否则直接覆盖该位置，保持数组长度不变但结尾更小
- 最终
tails.size()就是 LIS 长度（但tails不是实际子序列）
容易被忽略的边界和类型细节
用 vector<int> 存 tails 时，lower_bound 返回的是迭代器，别忘了减 begin() 转成下标；若用 int 存长度，遇到空输入要返回 0，而不是访问 tails[0]。
另外，C++ 中 lower_bound 要求容器已排序，而我们每次插入/覆盖都维持了单调性，所以没问题；但若误用 upper_bound，会破坏贪心策略 —— 因为我们要找的是“第一个不允许接续的位置”，不是“第一个严格大于的位置”。
真正难的不是写对模板，而是理解 tails[k] 的含义：它不代表某个真实子序列的第 k 个元素，而是所有长度为 k+1 的递增子序列中，最小可能的结尾值。
