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

示例:

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

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

 

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        if(n == 1) return 1;
        int len = 1;
        vector<int> dp;
        dp.push_back(nums[0]);
        for(int i = 1; i < n; i++){
            if(nums[i] > dp[len-1]){
                dp.push_back(nums[i]);
                len++;
            }
            else{
                int k = search(dp, nums[i]);
                dp[k+1] = nums[i];
            }
        }
        return len;
    }
    
    int search(vector<int> &arr, int x){
        int low = 0;
        int high = arr.size()-1;
        int k = (low+high)/2;
        while(!(arr[k] < x && x <= arr[k+1]) && high > low){
            if(arr[k+1] < x){
                low = k+1;
                k = (low+high)/2;
            }
            else if(x <= arr[k]){
                high = k-1;
                k = (low+high)/2;
            }
        }
        if(high > low) return k;
        else if(x <= arr[k]) return -1;
        else return 0;
    }
};

动态转移方程为： dp[i] = max(dp[j]) + 1, 其中 0<= j <= i-1， dp[i] 表示以 nums[i] 结尾的上升子序列的长度

根据DP方程，很显然你每次计算以 nums[i] 为结尾的上升子序列长度的时候，都要从 0 到 i-1遍历一下dp[]，这样下时间复杂度就是O(n²)了

其实可以用到贪心的思想降低时间复杂度：

想要上升子序列最长，那就是每次上升的时候增幅小一点

所以可以设置一个数组，其中记录每个长度下最后一个元素的最小值。

则每次计算 dp[i] 的时候，就可以不用遍历一遍dp了

而只需要对 dp 进行二分查找，这么一来，遍历dp的时间复杂度就由 O(n) 降到了 O(log n)，整体的时间复杂度降为 O(n log n)

为什么可以对dp进行二分查找呢？因为dp是单调递增的。