Longest Continuous Increasing Subsequence

Difficulty: Easy | Acceptance: 52.00% | Paid: No Topics: Array

Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (subarray).

A subsequence is continuous if it consists of consecutive elements in the original array.

• Examples
• Constraints
• Brute Force
• Dynamic Programming
• Single Pass (Optimal)

Examples

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 also an increasing subsequence, it is not continuous.

Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. 
Note that we must have strictly increasing elements, so [2,2] is not valid.

Constraints

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

Brute Force

Intuition We can check every possible starting index and expand outwards as long as the sequence remains strictly increasing. We keep track of the maximum length found during this process.

Steps

• Initialize max_len to 1 (minimum valid length).
• Iterate through each index i as the starting point.
• For each i, initialize curr_len to 1.
• Iterate j from i + 1 to the end of the array.
• If nums[j] > nums[j-1], increment curr_len.
• Otherwise, break the inner loop as the sequence is no longer increasing.
• Update max_len with the maximum of max_len and curr_len.
• Return max_len.

from typing import List

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        max_len = 1
        for i in range(n):
            curr_len = 1
            for j in range(i + 1, n):
                if nums[j] > nums[j - 1]:
                    curr_len += 1
                else:
                    break
            max_len = max(max_len, curr_len)
        return max_len

Complexity

• Time: O(n²) - In the worst case (strictly increasing array), we iterate through all subarrays.
• Space: O(1) - We only use a few variables for tracking lengths.
• Notes: Simple to implement but inefficient for large inputs.

Dynamic Programming

Intuition We can use a DP array where dp[i] represents the length of the longest continuous increasing subsequence ending at index i. If the current element is greater than the previous one, we extend the sequence; otherwise, we start a new sequence.

Steps

• Initialize a dp array of size n with all values set to 1.
• Initialize max_len to 1.
• Iterate from index 1 to n-1.
• If nums[i] > nums[i-1], set dp[i] = dp[i-1] + 1.
• Update max_len with the maximum of max_len and dp[i].
• Return max_len.

from typing import List

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        dp = [1] * n
        max_len = 1
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                dp[i] = dp[i - 1] + 1
            max_len = max(max_len, dp[i])
        return max_len

Complexity

• Time: O(n) - We traverse the array once.
• Space: O(n) - We maintain a DP array of size n.
• Notes: Better time complexity than brute force, but uses extra space.

Single Pass (Optimal)

Intuition Since we only need the previous length to calculate the current length, we don’t need the entire DP array. We can optimize space by just keeping track of the current sequence length and the maximum length found so far.

Steps

• Handle empty array case (return 0).
• Initialize max_len and curr_len to 1.
• Iterate from index 1 to n-1.
• If nums[i] > nums[i-1], increment curr_len.
• Else, reset curr_len to 1 (start a new sequence).
• Update max_len with the maximum of max_len and curr_len.
• Return max_len.

from typing import List

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        max_len = 1
        curr_len = 1
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                curr_len += 1
            else:
                curr_len = 1
            max_len = max(max_len, curr_len)
        return max_len

Complexity

• Time: O(n) - Single pass through the array.
• Space: O(1) - Only two integer variables are used.
• Notes: This is the most optimal solution for this problem.