674 最长连续子序列
动态规划
dp[i]表示以第i个元素结尾的最长连续子序列长度
与“300 最长递增子序列”不同在于:本题不需要遍历[0, i -1]找比nums[i]小的元素,只需要与nums[i - 1]比较即可
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
int res = 1;
for(int i = 1; i < n; i++){
if(nums[i] > nums[i - 1])
dp[i] = dp[i - 1] + 1;
res = max(res, dp[i]);
}
return res;
}
};
- 时间复杂度:O(n)
- 空间复杂度:O(n)
贪心
使用一个计数器,nums[i]比nums[i - 1]大就加一
否则,减一,重新计数
最后统计计数器最大值
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int n = nums.size();
int count = 1;
int res = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1])
count++;
else
count = 1;
res = max(res, count);
}
return res;
}
};
- 时间复杂度:O(n)
- 空间复杂度:O(1)