跳转至

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)