lis指子序列而非连续子数组，元素下标递增但可不连续；如[10,9,2,5,3,7,101,18]的lis长度为4；常见错误是误用连续递增判断；o(n²)dp解法定义dp[i]为以arr[i]结尾的lis长度。
最长增长子序列（LIS）不是“连续子数组”
很多人一看到“数组中找最长增长序列”，第一反应是用双指针扫连续递增段——但 LIS 指的是**子序列**（元素可不连续，但下标必须递增），比如 [10, 9, 2, 5, 3, 7, 101, 18] 的 LIS 是 [2, 3, 7, 18] 或 [2, 5, 7, 101]，长度为 4。这点不厘清，代码永远跑不对。
常见错误现象：for 循环里只比较 arr[i] > arr[i-1]，结果算出来是连续递增长度（比如上面例子会返回 2），而非真正 LIS 长度。
O(n²) 动态规划解法：适合理解与小规模数据
核心思路：定义 dp[i] 表示以 arr[i] 结尾的最长增长子序列长度。对每个 i，往前遍历所有 j ，若 <code>arr[j] ，就尝试更新 <code>dp[i] = max(dp[i], dp[j] + 1)。
-
dp数组初始全为 1（每个元素自身构成长度为 1 的子序列） - 必须从左到右逐个计算
dp[i]，因为依赖更小下标的dp[j] - 最终答案是
*max_element(dp.begin(), dp.end())，不是dp.back()
示例片段：
vector<int> arr = {10, 9, 2, 5, 3, 7, 101, 18};
vector<int> dp(arr.size(), 1);
for (int i = 1; i
<h3>O(n log n) 二分优化：必须用 <code>lower_bound</code>，不是 <code>upper_bound</code>
</h3>
<p>这个方法维护一个辅助数组 <code>tails</code>，其中 <code>tails[k]</code> 存放长度为 <code>k+1</code> 的所有 LIS 中**末尾最小的值**。它不存真实子序列，只用于推导长度。</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/shouce/1510" title="C函数速查手册（CHM版）"><img
src="https://img.php.cn/upload/manual/000/000/001/5d6de31fedca2993.png" alt="C函数速查手册（CHM版）" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/shouce/1510" title="C函数速查手册（CHM版）" class="overflowclass">C函数速查手册（CHM版）</a>
<p class="overflowclass">C函数速查手册（CHM版）</p>
</div>
<a rel="nofollow" href="/xiazai/shouce/1510" title="C函数速查手册（CHM版）" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<p>关键点在于插入逻辑：</p>
<ul>
<li>遇到新数 <code>x</code>，用 <code>lower_bound(tails.begin(), tails.end(), x)</code> 找第一个 ≥ <code>x</code> 的位置</li>
<li>把该位置替换为 <code>x</code>（保持 <code>tails</code> 严格递增）</li>
<li>如果 <code>x</code> 比所有元素都大，就 <code>push_back(x)</code>，此时 <code>tails.size()</code> 就是当前 LIS 长度</li>
</ul>
<p>错误做法：用 <code>upper_bound</code> 或手写二分时边界写错（比如 <code>left = 0, right = tails.size()</code> 但循环条件漏掉 =），会导致替换位置偏移，长度计算错误。</p>
<p>正确示例：</p>
<pre class="brush:php;toolbar:false;">
vector<int> tails;
for (int x : arr) {
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) {
tails.push_back(x);
} else {
*it = x;
}
}
int ans = tails.size(); // → 4
</int>
注意输入边界和类型：空数组、重复元素、负数都 OK
lower_bound 版本天然支持重复元素（因为找的是 ≥，重复时会覆盖前一个相同值，不影响长度），也兼容负数和空输入。
- 空数组：
tails保持为空，tails.size()返回 0 —— 正确 - 全等数组如
[5,5,5]：tails始终只存一个5，长度为 1 —— 符合“增长”（严格递增）定义 - 若题目要求“非降序”（允许相等），需改用
upper_bound并调整逻辑，但标准 LIS 定义是严格递增
真正容易被忽略的是：这个算法只返回长度，不构造实际子序列。如果后续需要还原路径，得回到 O(n²) DP 并额外记录 parent 数组 —— 别指望 tails 能反推出来。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
