300. Longest Increasing Subsequence

Question

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].

Solution

贪心算法

创建一个数组记录达到升序的长度时升序数列的最小末尾值。
如果想要增加数组的长度（即增加最大的升序数列长度），则新的数字必须要大于该数组最后一位的大小。
因此在这种情况下，该数组必然是单调递增的。

二分搜索

将第一个数字填入数组。
然后遍历数组，当新一项大于数组的最后一个值时，最大长度加一，并将其加入数组的尾部。
当新一项小于数组的最后一个值时，该数字需要与之前的数组组成新的升序数列。
我们可以替换掉之前数组中比该数字大的第一个数字，代表新组成的数组。（最长数组之间的数字无所谓，只记录最小的末尾值即可。）
我们可以用二分搜索查到该数字需要加入的index。然后替换掉数组中的数字。
单次二分搜索的时间复杂度为O($logn$)。总的时间复杂度为O($nlogn$)。

Code

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int len = 1;
        ans.add(nums[0]);
    
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > ans.get(ans.size()-1)){
                ans.add(nums[i]);
                len++;
            }
            else{
                int index = Collections.binarySearch(ans, nums[i]);
                if(index < 0){
                    ans.set(-(index+1), nums[i]);
                }
            }
        }
        return len;
    }
}

Solution 2

动态规划，创建一个数组dp[]用来记录最大长度，创建max记录最大值。
遍历，先将数组dp[]上的所有位置都填上1。
从0到i-1遍历j。当nums[i] > nums[j]时，更新dp[i]为dp[i]与dp[j]+1中的较大值。
当更新dp[i]时将其和max比较，如果比max大则更新max。
最后返回max值。时间复杂度为O($n_2$)

Code

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