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

• -104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

解题要点:

1. DP - Time O(n^2)

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

1. Binary Search - Time O(nlog(n))

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        List<Integer> res = new ArrayList<>();
        res.add(nums[0]);
        for(int i=1; i<nums.length; i++){
            if(nums[i] > res.get(res.size()-1)){
                res.add(nums[i]);   
            } else{
                int ind = binary(res,0,res.size()-1,nums[i]);
                res.set(ind,nums[i]);
            }
        }
        return res.size();
    }
    public int binary(List<Integer> res, int l, int h, int target){
        while(l <= h){
            int m = l + (h-l)/2;
            if(res.get(m) < target) l = m+1;
            else h = m-1;
        }
        return l;
    }
}