题意:
求最长增长的子序列的长度。
思路:
利用DP存取以i作为最大点的子序列长度。
Runtime: 20 ms, faster than 35.21% of C++ online submissions for Longest Increasing Subsequence.
class Solution
{
public:
int lengthOfLIS(vector<int> &nums)
{
if (nums.size() == )
return ;
vector<int> dp(nums.size(), );
dp[] = ;
int resNum = ;
for (int i = ; i < nums.size(); i++)
{
int curmaxNum = ; for (int j = ; j < i; j++)
{
if (nums[i] > nums[j])
curmaxNum = max(dp[j], curmaxNum);
}
dp[i] = curmaxNum + ;
resNum = max(dp[i], resNum);
}
return resNum;
}
};
解法二:
讨论区里的最优解:
利用一个容器去动态存储一个增长子序列,遍历Nums,对每一个nums[i],在容器中寻找是否有大于等于nums[i]的元素,若存在,则将改值替换为nums[i];
若不存在,则将nums[i]加入该容器,于是容器中的元素永远是 小于 关系的。
0ms.
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for(int i=; i<nums.size(); i++) {
auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
if(it==res.end()) res.push_back(nums[i]);
else *it = nums[i];
}
return res.size();
}
};