[LeetCode]300. 最长递增子序列

300. 最长递增子序列
给你一个整数数组 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
示例 3：

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

提示：

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

进阶：

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

• 最长上升子序列( L I S LIS LIS):Longest Increasing Subsequence
• 最长连续序列( L C S LCS LCS):Longest Consecutive Sequence
• 最长连续递增序列( L C I S LCIS LCIS):Longest Continuous Increasing Subsequence
• 最长公共子序列( L C S LCS LCS):Longest Common Subsequence

子串与子序列区别：子串不可跳跃，子序列可以跳跃，如 “AC”是“ABCDEFG”的子序列，而不是子串。 而“ABC”则是其子串

• d p [ i ] dp[i] dp[i]表示在区间 n u m s [ 0.... i ] nums[0....i] nums[0....i]区间范围内的最长上升子序列的长度

• 比较索引 i i i与其前面出现的某个位置 j j j的大小
  • 当 n u m s [ i ] < = n u m s [ j ] nums[i]<=nums[j] nums[i]<=nums[j]，说明 j j j处的值要比 i i i处的值的，要是形成子序列则是 n u m s [ 0... j , i ] nums[0...j,i] nums[0...j,i]这样的结果，这时候 j j j到 i i i不能形成递增，以 i i i结尾的子序列所形成的最长子序列的长度等价于以 j j j结尾的子序列所形成的最长子序列的长度，即 d p [ i ] = d p [ j ] dp[i]=dp[j] dp[i]=dp[j]
  • 当 n u m s [ i ] > n u m s [ j ] nums[i]>nums[j] nums[i]>nums[j]，说明 j j j处的值小于 i i i处值，形成的子序列是 n u m s [ 0... j , i ] nums[0...j,i] nums[0...j,i]这样的结果，这时候从 j j j到 i i i是递增的，这时候需要在长度上+1，即 d p [ i ] = d p [ j + 1 ] dp[i]=dp[j+1] dp[i]=dp[j+1]
  • 取上述两种情况的 m a x max max，动态转移方程为： d p [ i ] = M a t h . m a x ( d p [ i ] , d p [ j ] + 1 ) ∣ 0 < = j < i < n dp[i] = Math.max(dp[i], dp[j] + 1)|0<=j
  • 举例：如果遍历到 i i i位置，在 [ 0 − i ] [0-i] [0−i] 区间内有 [ 0 − j ] j < i [0-j] j

 for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

 public int lengthOfLIS(int[] nums) {
        //dp[i]: 到i为止 (对于所有 j in [0, i], 记录max length of increasing subsequence
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] dp = new int[len];
        int res = 0;
        for (int i = 0; i < len; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                //i 位置的数与[0,i]位置之间的数比较，如果大于进逻辑
                if (nums[i] > nums[j]) {
                    //等于dp[i]或者dp[j] + 1（j对应的值比i小）的最大值
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

 public int lengthOfLISII(int[] nums) {
        int n = nums.length;
        int[] tails = new int[n];
        int end = 0;
        for (int i = 0; i < n; i++) {
            int l = 0, r = end;
            while (l < r) {
                int m = (l + r) / 2;
                if (tails[m] < nums[i]) l = m + 1;
                else r = m;
            }
            tails[l] = nums[i];
            if (end == r) end++;
        }
        return end;
    }