300：最长上升子序列

问题描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明：

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n²) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

思路

这题是拥有最优子结构性质的。因为我们可以用dp[i]表示以nums[i]结尾的最长上升子序列的长度。
所以我们可以得到状态转移方程为：

dp[i] = max(dp[0~i-1])+1. if dp[0~i-1] < dp[i]

为啥是这样呢？因为dp[i]是以nums[i]结尾的最长上升子序列的长度。
搞完dp数组之后，遍历一遍，找出最大的返回即可。(方法一)

这题还可以继续优化。因为dp的时间复杂度为O(n²)。
我们可以用一个数组来保存之前的最长上升子序列的状态。
啥意思呢？

还不懂？其实是这样的。

[0]
[0,8]
[0,4]
[0,4,12]
[0,2]

每次我们都认为这个dp数组是存储了以当前元素结尾的最大上升子序列。我们想象成这个数组是可变的。每次我们加入新元素，都会构成一个以该元素为结尾的最大上升子序列。只不过我们为了时间复杂度和空间复杂度，而把这些行合并成了一行。即：
遍历到8时，成了[0,8]
遍历到4时，成了[0,4]
遍历到12时，成了[0,4,12]
遍历到2时，成了[0,2,12]
我们发现，从下往上看我标记为代码块的几个数组，合并之后是用手列的数组。就这么简单。(方法二)

方法一

Java版

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

方法二

Java版

public int lengthOfLIS(int[] nums){
        if(nums.length == 0) return 0;
        int res = 1;
        int[] resPool = new int[nums.length];
        resPool[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            if(resPool[res-1] < nums[i]){
                resPool[res++] = nums[i];
            }else{
                int left = 0, right = res-1, mid = (left+right)/2;
                while(left <= right){
                    mid = (left+right)/2;
                    if(resPool[mid] >= nums[i]){
                        right = mid-1;
                    }else{
                        left = mid + 1;
                    }
                }
                resPool[left] = nums[i];
                res = Math.max(left+1,res);
            }
        }
        return res;
    }