题目描述

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

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

输入输出

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

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

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

基本思路

方法一：动态规划

  1. 设置dp[i]的值代表以nums[i]结尾的最长子序列长度
  2. 判断条件：
    1. 当nums[i] > nums[j]时nums[i]可以接在nums[j]后边 此时最长子序列长度dp[j]+1
    2. 当nums[i] <= nums[j]时nums[i]无法接在nums[j]后边 不成立 跳过
    3. 因此转移方程为 $dp[i] = max(dp[i], dp[j]+1) \quad for \quad j \quad in \quad [0,i)$
  3. 初始状态：dp[i]中所有元素置1 意思是每个元素都可以单独成为子序列 此时长度为1
  4. 性能：
    1. 时复：$O(n^2)$ 遍历计算 dp 列表需 O(N) 计算每个 dp[i] 需 O(n)
    2. 空复：$O(n)$ dp列表占用线性大小额外空间

方法二：动态规划 + 二分查找

  1. 新建一个数组arr[]

  2. 对原序列进行遍历，将每位元素二分插入 arr[] 中。

    1. 如果 arr[] 中元素都比它小，将它插到最后。
    2. 否则，用它覆盖掉比它大的元素中最小的那个。

  3. 总之，思想就是让 arr[] 中存储比较小的元素。这样，arr[] 未必是真实的最长上升子序列，但长度是对的。

1
2
3
4
5
arr[]的变化:
[9, 0, 0, 0, 0, 0, 0, 0]
[2, 0, 0, 0, 0, 0, 0, 0]
[2, 3, 0, 0, 0, 0, 0, 0]
[2, 3, 7, 18, 0, 0, 0, 0]
  1. 性能：
    1. 时复：$O(nlogn)$ 数组 nums 的长度为 n，我们依次用数组中的元素去更新数组，而更新数组时需要进行 $O(logn)$ 的二分搜索，所以总时间复杂度为 $O(nlogn)$
    2. 空复：$O(n)$ 需要额外使用长度为 n 的数组

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 方法一
class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int res = 0;
        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

// 方法二
class Solution {
    public int lengthOfLIS(int[] nums) {
        int size = nums.length;
        if(size < 2) return size;
        int[] arr = new int[size];
        arr[0] = nums[0];
        int res = 1;
        for(int i = 1; i < size; i++) {
            if(nums[i] > arr[res-1]){
                arr[res] = nums[i];
                res++;
                continue;
            }
            int left = 0, right = res-1, mid;
            while(left <= right){
                mid = (left + right) / 2;
                if(arr[mid] >= nums[i]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
            arr[left] = nums[i];
        }
        return res;
    }
}