最长递增子序列

最长递增子序列到底在问什么

题目给一个数组 nums，要求挑出一个严格递增的子序列，返回它的最长长度。两个关键词都藏着坑：子序列不要求连续，可以跳着选，只要保持原数组里的先后顺序；严格递增意味着相等不算。比如 nums=[10,9,2,5,3,7,101,18]，最长的一条是 2、5、7、101，答案是 4——这四个数并不相邻。

为什么暴力枚举子序列行不通

最直接的想法是枚举所有子序列逐个检查：每个数都有选或不选两种可能，n 个数就有 2 的 n 次方个子序列，指数级的量根本跑不完。慢的根源是大量重复劳动——很多子序列共享同一段前缀，它们的递增性被反复检查。

换个角度看：任何一条递增子序列总要以某个数收尾。而以 nums[i] 收尾的最优解，只取决于它前面那些更小的数各自的最优解——这个观察让问题可以从左往右递推，动态规划由此成形。

dp 数组为什么定义成以 i 结尾而不是前 i 个

dp[i] 的定义是：以 nums[i] 结尾的最长严格递增子序列的长度。注意不能定义成前 i 个数里的最长长度——那样的状态丢了子序列的结尾是谁，来了新数判断不了能不能接，转移写不出来。固定住结尾，新旧状态之间才能比较、才能拼接。

初始值是 dp 全填 1：任何一个数自己就是长度为 1 的子序列，这是每个位置的保底答案，写成 0 会从根上算错。

转移方程为什么成立

算 dp[i] 时，往前看每一个 j：只要 nums[j] < nums[i]，就可以把 nums[i] 接在那条以 nums[j] 结尾的最长子序列后面，得到长度 dp[j] + 1。在所有合法的 j 里挑最大的那个，就是 dp[i] = max(dp[i], dp[j] + 1)。

它为什么对？因为以 nums[i] 结尾的任何一条递增子序列，去掉 nums[i] 之后，剩下的部分必然以某个更小的数 nums[j] 结尾，而且那部分不会比 dp[j] 更长——这就是无后效性：前面怎么选出来的不重要，只要知道以 j 结尾的最优长度就够了。把所有候选 j 都试一遍取最大，最优解一定不会漏。

答案为什么是 max(dp) 而不是最后一格

填完整个 dp 数组后，答案是 max(dp)，不是 dp[n-1]。原因很简单：最长的递增子序列不一定以最后那个数结尾。上面的例子里最大值出现在 101 的位置，如果数组以一个很小的数收尾，最后一格甚至可能是 1。直接返回最后一格是这道题最常见的错误。

复杂度多少，还能不能更快

时间复杂度 O(n²)：每个位置 i 都要往前扫一遍全部 j，两层循环。空间 O(n)，一个 dp 数组。两个易错点再强调一次：严格递增的判断必须写 nums[j] < nums[i]，写成小于等于会把相等的数也接进去；dp 初值必须是 1 不是 0。

面试若追问更优解法：维护 tails 数组，tails[k] 存长度为 k+1 的递增子序列的最小结尾，每个新数二分查找该替换或追加的位置，tails 的长度就是答案，整体 O(n log n)。先讲清 O(n²) 动态规划，再谈这个贪心加二分的优化，层次更好。