LeetCode300：最长递增子序列

要求

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。

题目分析

需要对「子序列」和「子串」这两个概念进行区分；

• 子序列（subsequence）：子序列并不要求连续，例如：序列 [4, 6, 5] 是 [1, 2, 4, 3, 7, 6, 5] 的一个子序列；
• 子串（substring、subarray）：子串一定是原始字符串的连续子串。

子序列中元素的 相对顺序 很重要，子序列中的元素 必须保持在原始数组中的相对顺序。如果把这个限制去掉，将原始数组去重以后，元素的个数即为所求；

思路

方法一：动态规划
状态定义：dp[i] 表示：以 nums[i] 结尾 的「上升子序列」的长度。 这个定义中 nums[i] 必须被选取，且必须是这个子序列的最后一个元素；
初始化：dp[i] = 1，1 个字符显然是长度为 1 的上升子序列。
返回数组dp的最大值

public class LeetCode300 {
    public int lengthOfLIS(int[] nums) {
        //边界判断
        if (nums.length < 2){
            return nums.length;
        }

        int[] dp = new int[nums.length];
        //dp数组初始值为1
        Arrays.fill(dp,1);

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                //前面小于后面的，则证明有以nums[i]结尾的上升序列，比较最长上升子序列的长度
                if (nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
        }

        int res = 0;
        //循环pd数组，寻找到最长上升子序列的长度
        for (int i = 0; i < nums.length; i++) {
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}
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

时间复杂度：O(N^2)，这里 N 是数组的长度；
空间复杂度：O(N)，要使用和输入数组长度相等的状态数组；

---

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

1、状态定义：dp[i] 表示：长度为 i + 1 的 所有 上升子序列的结尾的最小值。
解释： dp[0] 表示长度为 1 的所有上升子序列中，结尾最小的元素的数值。以题目中的示例为例 [10, 9, 2, 5, 3, 7, 101, 18] 中，容易发现长度为 2 的所有上升子序列中，结尾最小的是子序列 [2, 3] ，因此 tail[1] = 3；
下标和长度有数值为 1 的偏差；

---

2、说明：
1、在遍历数组 nums 的过程中，如果新数num大于有序数组 dp的最后一个元素，就把 num 放在有序数组 dp 的后面，否则进入第 2 点；

2、在有序数组 dp中查找第 1 个等于大于 num 的那个数，试图让它变小：

• 如果有序数组 dp 中存在 等于 num 的元素，什么都不做，因为以 num 结尾的最短的「上升子序列」已经存在；
• 如果有序数组 dp 中存在 大于 num 的元素，找到第 1 个，让它变小，这样我们就找到了一个 结尾更小的相同长度的上升子序列。

3、初始化：遍历第 1 个数 nums[0]，直接放在有序数组 dp 的开头 tail[0] = nums[0]

4、返回有序数组dp的长度即可

public class LeetCode300 {
    public int lengthOfLIS(int[] nums) {
        if (nums.length < 2){
            return nums.length;
        }

        //定义dp数组：长度为i + 1的上升子序列的末尾最小值；第一个值直接放到dp有序数组开头
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        //定义有序数组dp的最后一个已经赋值元素的索引
        int end = 0;

        for (int i = 1; i < nums.length; i++) {
            //数组中的元素比有序数组dp中最后一个元素还大的话，end先加1，添加到那个元素后面
            if (nums[i] > dp[end]){
                end++;
                dp[end] = nums[i];
            }else {
                //使用二分查找在有序数组dp中，找到第一个大于等于nums[i]元素的数，尝试让那个元素更小
                int left = 0,right = end;
                while (left < right){
                    //这里是向下取整
                    int mid = left + (right - left)/2;
                    //如果有序数组的中位数比数组nums[i]的元素小的话，当前中位数肯定不是目标数，移动位置
                    if (dp[mid] < nums[i]){
                        left = mid + 1;
                    }else {
                        right = mid;
                    }
                }
                dp[left] = nums[i];
            }
        }
        //end是有序数组中的最后一个元素，+1之后返回长度，因为下标是从0开始的
        end++;
        return end;
    }
}
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

时间复杂度：O(NlogN)，遍历数组使用了 O(N)，二分查找法使用了 O(logN)。
空间复杂度：O(N)