# 0300. Longest Increasing Subsequence
###### tags: `Leetcode` `Medium` `Binary Search` `Dynamic Programming` `Greedy` `Longest Increasing Subsequence`
Link: https://leetcode.com/problems/longest-increasing-subsequence/
## 思路
### Binary Search $O(NlogN)$ $O(N)$
最佳解的核心是**直接建一个 increasing sequence**
每一个新的元素来，如果比现在的increasing sequence的最大值大，就直接往后加，
否则binary search找应该要替换的元素（第一个比它自己大的元素）

后来重新做这道题的时候原本想要用stack解，遇到peek比现在的值大就pop，然后在过程中记录最大的stack size，后来发现不行，因为如果遇到$[0,1,0,3,2,3]$这样的测资，最长的subsequence应该是$[0,1,2,3]$，但是按这种方法，答案就会变成$[0,2,3]$
说明**用stack维持单调栈只适合解决找左边/右边的最大/小值，找一个元素，而不是找整个序列**
**注意line20要用<，而不是<=**
### DP $O(N^2)$ $O(N)$
状态定义：照抄问题 **```dp[i] => s[1:i]```里以```s[i]```结尾的最长的递增子序列的长度**。
状态的转移：寻找最优的前驱状态j，将```dp[i]```与```dp[j]```产生联系。
## Code
### Binary Search $O(NlogN)$ $O(N)$

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        seq = []

        def findPos(num):
            start, end = 0, len(seq)
            while start<end:
                mid = start+(end-start)//2
                if seq[mid]<num:
                    start = mid+1
                else:
                    end = mid
            return start

        for num in nums:
            if not seq or num > seq[-1]:
                seq.append(num)
            else:
                # find the smallest element in the list that is bigger than num
                # and then replace it
                seq[findPos(num)] = num
        return len(seq)

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for(int i = 0;i < nums.length;i++){
            if(res.size() == 0){
                res.add(nums[i]);
                // len++;
            }
            else{
                int currMax = res.get(res.size()-1);
                if(nums[i]>currMax){
                    res.add(nums[i]);
                    // len++;
                }   
                else{
                    int start = 0;
                    int end = res.size();
                    while(start<end){
                        int mid = (start+end)/2;
                        if(res.get(mid)<nums[i]){
                            start = mid+1;
                        }
                        else{
                            end = mid;
                        }
                    }
                    res.set(start, nums[i]);
                }
            }
        }
        return res.size();
    }
}

### DP

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