[leetcode] 300. Longest Increasing Subsequence (Medium)

时间:2024-08-11 13:07:26

题意:

求最长增长的子序列的长度。

思路:

利用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();
}
};