300. Longest Increasing Subsequence

# Medium（非常经典，一定要会）

This is type of sequence DP. 前i个是否是LIS. 这也叫区间动态规划，下角标从小到大计算，因为后面的元素基于前面的元素。

From index of 0 to n, record longest increasing subsequence in a list. f[i] means the longest increasing subsequence ending with nums[i].

Solution 1: time complex = $O(n^2)$

1. Define f[i], records the longest increasing subsequence ending with nums[i]

2. Compute f[i] from index of 0, if nums[j] < nums[i] (j < i), f[i]=max(f[i], f[j]+1)

3. Loop f[i] to find biggest value, return it

Python(O(n^2))

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # edge case
        if len(nums) <= 1:
            return len(nums)
        
        f = [1]*len(nums) # f[i] means LIS ending with nums[i]
        for i in range(0, len(nums)):
            for j in range(0, i):
                if nums[j] < nums[i]:
                    f[i] = max(f[i], f[j]+1)
        
        result = f[0]
        for i in range(1, len(f)):
            if f[i] > result:
                result = f[i]
                
        return result

Java(O(n^2))

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

Solution 2: time complex = $O(nlgn)$

Save time when looking for the biggest element nums[j] less than nums[i] by binary search.

Java

class Solution {
    public int lengthOfLIS(int[] nums) {
        // sub is always an ascending list
        ArrayList<Integer> sub = new ArrayList<>();
        sub.add(nums[0]);
        for(int i = 1; i < nums.length; i ++) {
            if(nums[i] > sub.get(sub.size() - 1))
                sub.add(nums[i]);
            else {
                int x = insertPosition(sub, nums[i]);
                sub.set(x, nums[i]);
            }
        }
        return sub.size();
    }
    
    // fint the element is just lagger than target
    // then replace it with target
    private int insertPosition(ArrayList<Integer> sub, int target) {
        int left = 0, right = sub.size() - 1;
        while(left < right) {
            int mid = left + (right - left)/2;
            if(target == sub.get(mid))
                return mid;
            else if(target > sub.get(mid))
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
}

Second Tab