LeetCode Longest Increasing Subsequence （LIS O(nlogn)）

 

题意：

　　给一个数组，求严格递增的最长递增子序列的长度。

 

思路：

　　开销是一个额外的O(n)的数组。lower_bound(begin,end,val)的功能是：返回第一个大于等于val的地址。

 

 

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty())    return 0;
        int *p=new int[nums.size()];
        p[0]=nums[0];
        int len=0;
        for(int i=1; i<nums.size(); i++)    
        {
            if(nums[i]>p[len])
                p[++len]=nums[i];
            else
                *lower_bound(p,p+len+1,nums[i])=nums[i];
        }
        delete []p;
        return ++len;
    }
};