题目
DP解法
思路
开一个长度与原数组相同的数组dp，初始值dp[0]=1。dp数组元素的含义是：到当前索引为止，最大的递增子序列长度。接下来开始遍历数组，设当前索引为index，在0..index范围内，找出小于当前元素的那些元素，它们对应的dp值中的最大值+1，即为本轮结果。遍历完成后，dp数组中的最大值即为答案。
复杂度分析
O(n2)
实现
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size()<2) return nums.size();
vector<int> dp(nums.size());
dp[0] = 1;
int ans = dp[0];
for(int i = 0; i < dp.size(); i++) {
int maxval = 0;
for(int j = i-1 ; j >= 0; j--) {
if(nums[j] < nums[i]) {
maxval = max(maxval,dp[j]);
}
}
dp[i] = maxval + 1;
ans = max(ans,dp[i]);
}
return ans;
}
};
贪心+二分解法
思路
开一个tails数组，tails[1] = nums[0]，元素的含义为：当递增子序列的长度为index时，对应长度子序列的最后一个值(我们希望这个值尽可能小)。然后开始遍历原数组，如果当前元素大于 tails数组最后一个有效元素(最后一个非初值的元素)，则说明子序列长度可以增长，tails[++index] = 当前元素。否则，二分查找tails数组中最后一个小于当前元素的那个元素索引，更新tails[这个索引+1] = 当前元素。最后的index即为答案。
复杂度分析
O(nlogn)
实现
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size()<2) return nums.size();
vector<int> tails(nums.size()+1);
int len = 1;
tails[len] = nums[0];
for(int i=1;i<nums.size();i++) {
if(tails[len]<nums[i]) tails[++len] = nums[i];
else {
int pos = 0, begin = 1,end = len;
while(begin<=end) {
int mid = begin + (end-begin)/2;
if(tails[mid]<nums[i]) {
pos = mid;
begin = mid+1;
} else {
end = mid-1;
}
}
tails[pos+1] = nums[i];
}
}
return len;
}
};
一种更简洁的写法
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> minnums;
for (int v : nums) {
if (minnums.size() == 0 || v > minnums.back())
minnums.push_back(v);
else {
auto it = lower_bound(minnums.begin(), minnums.end(), v);
*it = v;
}
}
return minnums.size();
}
};