echo

任生命穿梭 时间的角落

0%

最长递增子序列

Posted on Edited on In Valine:

300. 最长递增子序列

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

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列长度，nums[i] 必须被选择。

从小到大计算 dp 数组的值，在计算 dp[i] 之前，我们已经计算出 dp[0 … i - 1]的值，状态转移方程为：
$$
dp[i] = max(dp[j]) + 1, 其中 0 \leq j<i 且nums[j] < nums[i]
$$
即考虑往 dp[0 … i - 1]中的最长上升子序列后面再加一个 nums[i]，此时 nums[i]必须大于前面的最长子序列中的最后一个元素，假设我们选择最长上升子序列 dp[j]，nums[i] 就必须大于 nums[j]。

最后整个数组的最长上升子序列即为所有 dp[i] 中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int[] dp = new int[nums.length];
        int maxLen = 1;
        dp[0] = 1;
        for(int i = 1; i < nums.length; i++){
            dp[i] = 1;
            //尝试在dp[0 ... i-1]中找一个最长递增子序列
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }
}
  • 时间复杂度O(n^2)
  • 空间复杂度O(n)