lc300.最长递增子序列

题目

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

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

示例 1：

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

示例 2：

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

提示：

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

解法一：动态规划

最容易想到的就是用f[i]来表示前i个元素上升子序列的最大长度。

时间复杂度：O(n^2)；

空间复杂度：O(n);

代码如下：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int res = 1;
        for(int i = 0; i < n; i++) {
            f[i] = 1;
            for(int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
            res = Math.max(res, f[i]);
        }
        return res;
    }
}

运行结果：

解法二：贪心+二分

观察子序列：

10 9 2 5 3 7 101 18

可以用一个数组f[i]来表示子序列长度为i的最小某位元素，比如f[1]表示长度为1的递增子序列的最小元素，遍历到nums[0]时,f[1] = 10，当遍历到nums[1]时,由于f[1] = 9,只需要保存所有长度为1的递增子序列的最后一个元素的最小值（这里10， 9可以看成两个递增子序列）；同理，当遍历到nums[2]时，f[1] = 2，当nums[3]时，这是nums[3] > f[1]，则一个长度为2的子序列长度可以放入f[2]中。对于nums[3] <= f[i]时，我们需要在f数组中找到第一个大于等于nums[i]的数，并进行替换。

时间复杂度：O(nlogn)

空间复杂度：O(n)

代码如下：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] f = new int[nums.length + 1];
        int cnt = 0;
        f[0] = -0x3f3f3f3f;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > f[cnt]) f[++cnt] = nums[i];
            else {
                int l = 1, r = cnt;
                while(l < r) {
                    int mid = l + r >> 1;
                    if(f[mid] >= nums[i]) r = mid;
                    else l = mid + 1;
                }
                f[l] = nums[i];
            }
        }
        return cnt;
    }
}