动态规划O(N^2)

dp[i]含义： 以i结尾的最长递增子序列长度

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

优化O(N * logN)

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小

• dp含义不变
• ends数组用来加速每一步的dp而存在的
  • ends数组一开始全是无效区
  • ends[i]的含义： 代表所有长度为 i + 1的递增子序列的最小结尾是ends[i]

• 接下来遍历到原数组1位置的数1了， 在ends里找≥1最左的位置，更新
  • 
  • 1所在的有效区连同左边有几个数就是它的dp值
  • 
• 接下来遍历到原数组2位置的数6了，在ends里找不到≥6最左的位置，扩充有效区（扩充有效区代表长度为1的递增子序列可以被扩张成长度为2）
  • ‘
  • 6所在的有效区连同左边有几个数就是它的dp值
  • 
• 
• 
• 
• 
• 

时间复杂度分析

来了一个num，你就去ends二分找到≥num最左的数，然后做操作，然后看它及其左边有几个数，就更新dp值
时间复杂度O（N * logN）

//O（N * logN）
    public int lengthOfLIS2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] ends = new int[nums.length];
        ends[0] = nums[0];
        int right = 0; // 0..right是有效区
        int l = 0;
        int r = 0;
        int m = 0;
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            l = 0;
            r = right;
            while (l <= r) {
                m = (l + r) / 2;
                if (nums[i] > ends[m]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            right = Math.max(right, l);
            ends[l] = nums[i];
            max = Math.max(max, l + 1);
        }
        return max;
    }