题意:
给一个数组,求严格递增的最长递增子序列的长度。
思路:
开销是一个额外的O(n)的数组。lower_bound(begin,end,val)的功能是:返回第一个大于等于val的地址。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.empty()) return ;
int *p=new int[nums.size()];
p[]=nums[];
int len=;
for(int i=; i<nums.size(); i++)
{
if(nums[i]>p[len])
p[++len]=nums[i];
else
*lower_bound(p,p+len+,nums[i])=nums[i];
}
delete []p;
return ++len;
}
};
AC代码