300. LIS

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int flag [] = new int [len];
        int ans = 0;
        for(int i = 0 ; i < len ; i++){
            flag[i] = 1;
            for(int j = 0 ; j < i  ;j++){
                if(nums[i]>nums[j]){
                    flag[i] = Math.max(flag[i],flag[j]+1); //flag[i] 不能用1代替
                }
            }
            ans = Math.max(ans,flag[i]);
        } 
        return ans;
    }
}

O(nlogn)
https://www.bilibili.com/video/av60528477
https://www.bilibili.com/video/av57283963/

• 可以观察到，如果出现新的最大值，整个数组的长度+1，如果遇到新的最大值的最小值，那么就会更新dp的最大值，因为后面出现的最大值一定可以被加到之前的连续上升subsequence当中，所以这样的dp是数据可能不对，但是dp长度就代表我没呢最长可能会的list长度

• leetcode自带题解库
  
  

    public int lengthOfLIS(int[] nums) {
        // O(n) 二分+dp
        int[] top = new int[nums.length];
        int piles = 0;
        for (int i = 0; i < nums.length; i++) {
            int poker = nums[i];
            int left = 0, right = piles;
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
  
            if (left == piles)
                piles++;
            top[left] = poker;
        }
        return piles;
    }