0300. Longest Increasing Subsequence

---

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

---

解法1

定义一维数组dp, dp[i]表示到一定包括 i 的时候的递增数列的元素个数.

对于i, 如果j< i,并且 nums[j] < nums[i], 那么dp[i] 就取 dp[j] +1 和dp[i] 中的较大值.

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

---

定义辅助数组m,长度为n+1.

对于input来说,假设有长度为 j 的递增数列, 那么可能存在多个不同的数列,那么用m[ j ] 来保存着多个不同数列中,最小的最大值在nums中对应的下标.

定义主数组p,长度为n.

p[ k ]表示以nums[ k ] 为最大值的递增数列的前一个元素在nums中的下标.每次更新m[ j ] 的时候,将m[j - 1]存入p[ k ].

需要注意的是p的下标和nums的下标是一一对应的,所以在最后求LIS的时候,可以直接用 k = p[k] 来循环得到前一个数字.

定义变量l, 表示到目前为止递增数列的最大值

解法2

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        
        int n = nums.length;
        // m[j] 表示长度为j的递增数列中,最小的最大值在nums中的下标
        int[] m = new int[n+1];
        // 到目前位置的递增数列的最大值
        int l = 0;
        for(int i = 0; i < n; i++){
            // 二叉搜索,在已知的递增数列的长度中找到当前nums[i]对应的位置
            int lo = 1, hi = l,newl = 1;
            while(lo <= hi){
                int mid = (lo + hi) / 2;
                if(nums[m[mid]] < nums[i]){
                    lo = mid + 1;
                    newl = lo;
                }else
                    hi = mid - 1;
            }
            
            // 替换掉长度为newl的递增数列的最大值在nums中的下标
            m[newl] = i;
            if(newl > l)
                l = newl;
        }
        return l;
    }
}