线性动态规划：最长递增子序列 题目描述 给定一个整数数组 nums，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，不要求连续，但必须保持元素间的相对顺序。例如，对于数组 [ 10,9,2,5,3,7,101,18]，最长递增子序列是 [ 2,3,7,101] 或 [ 2,5,7,101 ]，因此长度是 4。 解题过程 问题分析 我们需要找出一个最长的子序列，其中每个元素都严格大于前一个元素。由于子序列不要求连续，直接枚举所有可能的子序列（时间复杂度 O(2^n)）不可行。动态规划通过存储中间结果来避免重复计算。 定义状态 定义 dp[ i] 表示以第 i 个元素结尾的最长递增子序列的长度。例如，对于 nums[ i]，dp[ i] 记录了所有可能以 nums[ i ] 结尾的递增子序列中的最大长度。 状态转移方程 对于每个位置 i，我们需要检查所有在 i 之前的元素 j（0 ≤ j < i）： 如果 nums[ i] > nums[ j]，说明 nums[ i] 可以接在以 nums[ j] 结尾的递增子序列之后，形成更长的子序列。此时，dp[ i] = max(dp[ i], dp[ j ] + 1)。 如果不存在这样的 j（即所有前面的元素都大于等于 nums[ i]），那么 nums[ i] 自身构成一个子序列，dp[ i ] = 1。 综合以上： dp[ i] = max(dp[ i], dp[ j] + 1) 对所有 j < i 且 nums[ j] < nums[ i] ，初始值 dp[ i ] = 1。 计算顺序与示例 按 i 从 0 到 n-1 顺序计算每个 dp[ i]。以 nums = [ 10,9,2,5,3,7,101,18 ] 为例： i=0: nums[ 0]=10，前面无元素，dp[ 0 ]=1。 i=1: nums[ 1]=9，前面元素 10≥9，无法接续，dp[ 1 ]=1。 i=2: nums[ 2]=2，前面元素均≥2，dp[ 2 ]=1。 i=3: nums[ 3]=5，检查 j=2（元素2<5），dp[ 3]=max(1, dp[ 2 ]+1)=2。 i=4: nums[ 4]=3，检查 j=2（元素2<3），dp[ 4]=max(1, dp[ 2 ]+1)=2。 i=5: nums[ 5]=7，检查 j=2（2→dp=1+1=2）、j=3（5→dp=2+1=3）、j=4（3→dp=2+1=3），取最大值 dp[ 5 ]=3。 i=6: nums[ 6]=101，可接在任意元素后，取最大 dp[ j]+1=dp[ 5]+1=4，dp[ 6 ]=4。 i=7: nums[ 7]=18，可接在 j=5（7→3+1=4）或 j=3（5→2+1=3）等，最大值 dp[ 7 ]=4。 最终，所有 dp[ i ] 中的最大值为 4。 复杂度分析 时间复杂度：O(n²)，需要两层循环遍历所有 i 和 j。 空间复杂度：O(n)，用于存储 dp 数组。 优化思路（补充） 可通过贪心+二分查找将时间复杂度优化到 O(n log n)，但本题重点在于线性动态规划的基本解法，此处不展开。