最长递增子序列：动态规划与贪心解法

最长递增子序列

问题简介

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

• 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
• 严格递增 指的是对于子序列中任意相邻两个元素 a[i] < a[i+1]。

示例说明

示例 1

输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,18]，因此长度为 4。

示例 2

输入：nums = [0,1,0,3,2,3] 输出：4

示例 3

输入：nums = [7,7,7,7,7,7,7] 输出：1

解题思路

方法一：动态规划（DP）—— O(n²)

思路步骤：

1. 定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
2. 初始时，每个 dp[i] = 1（每个元素自身构成长度为 1 的子序列）。
3. 对于每个 i，遍历所有 j < i：
   • 如果 nums[j] < nums[i]，则可以将 nums[i] 接在以 nums[j] 结尾的子序列后，即 dp[i] = max(dp[i], dp[j] + 1)。
4. 最终答案是 max(dp[0...n-1])。

时间复杂度较高，但逻辑清晰，适合理解 LIS 本质。

方法二：贪心 + 二分查找 —— O(n log n)

思路步骤：

1. 维护一个数组 tails，其中 tails[k] 表示长度为 k+1 的递增子序列的最小末尾元素。
2. 遍历 nums 中每个元素 x：
   • 如果 x 大于 tails 的最后一个元素，则直接追加（说明可以延长当前最长子序列）。
   • 否则，在 tails 中使用二分查找找到第一个 ≥ x 的位置，并用 x 替换它（保持 tails 的性质）。
3. tails 的长度即为 LIS 的长度。

关键点：tails 数组本身不一定是真实的 LIS，但它能正确维护 LIS 的长度。

代码实现

// 方法一：动态规划 O(n²)
class Solution {
    public   {
           nums.length;
        [] dp =  [n];
        java.util.Arrays.fill(dp, );
           ;
         (   ; i < n; i++) {
             (   ; j < i; j++) {
                 (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + );
                }
            }
            res = Math.max(res, dp[i]);
        }
         res;
    }
}


  {
       {
        java.util.List<Integer> tails =  .util.ArrayList<>();
         ( x : nums) {
               , right = tails.size();
             (left < right) {
                   (left + right) / ;
                 (tails.get(mid) < x) {
                    left = mid + ;
                }  {
                    right = mid;
                }
            }
             (left == tails.size()) {
                tails.add(x);
            }  {
                tails.set(left, x);
            }
        }
         tails.size();
    }
}