因为dp[i]定义为“以nums[i]结尾的最长递增子序列长度”，才能确保状态可转移：j
为什么 dp[i] 定义成“以 nums[i] 结尾的最长递增子序列长度”是关键
因为只有这样，状态才能被后续位置复用：dp[j]（j ）可直接参与转移，而若定义为“前 <code>i 个元素的 LIS 长度”，就无法保证末尾对齐，没法安全转移。
常见错误是把 dp[i] 当成全局最优，结果在更新时漏掉“必须以当前元素结尾”这一约束，导致转移逻辑错乱。
-
dp[i]初始值设为 1（每个元素自身构成长度为 1 的递增子序列） - 对每个
i，需遍历所有j ，仅当 <code>nums[j] 时才考虑 <code>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 <p>注意：<code>dp[i]</code> 只依赖更小下标的 <code>dp[j]</code>，所以从左到右扫描安全；但若数组为空，要提前判 <code>n == 0</code>，否则 <code>max_element</code> 行为未定义。</p><div class="aritcle_card flexRow artxards"> <div class="artcardd flexRow"> <a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a> <div class="aritcle_card_info flexColumn"> <a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a> <p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p> </div> <a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span> </a> </div> </div> <h3>为什么 <code>lower_bound</code> 能把时间优化到 O(n log n)</h3> <p>本质是维护一个“可能成为某长度 LIS 结尾的最小值”数组 —— 它天然有序，支持二分。每次用 <code>nums[i]</code> 去替换第一个 ≥ 它的数，等价于“尝试延长某个已有长度的序列，或更新该长度的结尾下界”。</p> <ul> <li>不存完整子序列，只存每个长度对应的最小结尾值，数组严格递增</li> <li> <code>lower_bound(tails.begin(), tails.end(), nums[i])</code> 找到第一个不能接在 <code>nums[i]</code> 后面的位置</li> <li>若找到末尾，则 push_back；否则直接覆盖该位置，保持数组长度不变但结尾更小</li> <li>最终 <code>tails.size()</code> 就是 LIS 长度（但 <code>tails</code> 不是实际子序列）</li> </ul> <h3>容易被忽略的边界和类型细节</h3> <p>用 <code>vector<int></int></code> 存 <code>tails</code> 时，<code>lower_bound</code> 返回的是迭代器，别忘了减 <code>begin()</code> 转成下标；若用 <code>int</code> 存长度，遇到空输入要返回 0，而不是访问 <code>tails[0]</code>。</p> <p>另外，C++ 中 <code>lower_bound</code> 要求容器已排序，而我们每次插入/覆盖都维持了单调性，所以没问题；但若误用 <code>upper_bound</code>，会破坏贪心策略 —— 因为我们要找的是“第一个不允许接续的位置”，不是“第一个严格大于的位置”。</p> <p>真正难的不是写对模板，而是理解 <code>tails[k]</code> 的含义：它不代表某个真实子序列的第 <code>k</code> 个元素，而是所有长度为 <code>k+1</code> 的递增子序列中，最小可能的结尾值。</p></int>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
