LIS算法

• 定义dp[i]为：以ai为末尾的最长上升子序列的长度
• dp[i]包括：
  • 只包括自己，也就是它前面的元素全部都比它大，例子{7,9,6,10,7,1,3},则dp[6] == 1 第六个是1
  • 为了保证上升子序列尽可能长，那么就有dp[i]尽可能大，但是再保证dp[i]尽可能大的基础上，还得保证序列上升。则ai > aj && i > j ?dp[j] +1 : 1 , 当第i个数前面有一个第j个数满足条件，找最大dp[j] ，说明ai元素可以接在aj元素的后面，且最长。

O( )

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);
                }
            }
            ans = Math.max(ans,flag[i]);
            System.out.println(ans+" "+flag[i]);
        } 
        return ans;
    }
}

LIS的nlogn优化【贪心】

• 例子{4,2,3,1,2,3,5}这个序列
• 开一个数组arr[10]
• 第一个数是4，先加进去 ->{4}
• 第二个数是2，比4小，2替换4 ->{2}
• 第三个数是3，比2大，加入 ->{2,3}
• 第四个数是1，比3 、 2还小

O(nlogn)

    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;
    }