Skip to content

Longest Continuous Increasing Subsequence⚓︎

Link

Description⚓︎

Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.

A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].

Example 1:

  • Input: nums = [1,3,5,4,7]
  • Output: 3
  • Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3. Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element 4.

Example 2:

  • Input: nums = [2,2,2,2,2]
  • Output: 1
  • Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly increasing.

Constraints:

  • 1 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9

Solution⚓︎

Dynamic Programming⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        dp[0] = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(n)\).

Greedy⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int res = 1;
        int count = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) count++;
            else count = 1;

            if (count > res) res = count;
        }
        return res;
    }
};
  • Time complexity: \(O(n)\);
  • Space complexity: \(O(1)\).