We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Continuous Increasing Subsequence

Number: 674

Difficulty: Easy

Paid? No

Companies: Meta, Yandex, Apple, Amazon

Problem Description

Given an unsorted array of integers, return the length of the longest continuous strictly increasing subsequence (subarray). A continuous increasing subsequence is defined by a range [l, r] where for every index i from l to r-1, nums[i] < nums[i+1].

Key Insights

  • The subsequence must be continuous and strictly increasing.
  • A single element is considered an increasing subsequence of length 1.
  • Use a single scan through the array to track the length of the current increasing segment.
  • If the current element is greater than the previous one, extend the current segment; otherwise, reset the segment length.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of elements in the array, since we traverse the list once.
Space Complexity: O(1) - constant extra space is used.

Solution

We traverse the array while maintaining two variables: one for the current length of the increasing segment and one for the maximum length found so far.

  • Start by initializing both counters to 1 because a single element is a valid subsequence.
  • For each element from the second element onward, compare it to the previous element.
  • If the current element is greater than the previous one, increment the current segment length.
  • If not, update the maximum length if the current segment is longer, then reset the current segment length to 1.
  • After the loop, ensure to update the maximum length one last time in case the longest segment is at the array end.

Code Solutions

# Python solution for finding the longest continuous increasing subsequence

def findLengthOfLCIS(nums):
    # Edge case: if the list is empty, return 0 (though constraints say length >= 1)
    if not nums:
        return 0

    current_length = 1  # current increasing sequence length
    max_length = 1      # maximum increasing sequence length found

    # Iterate from the second element to the end of the list
    for i in range(1, len(nums)):
        # Check if the current element is greater than the previous element
        if nums[i] > nums[i - 1]:
            current_length += 1  # Extend current sequence
        else:
            # Update max_length if current sequence ended
            max_length = max(max_length, current_length)
            current_length = 1  # Reset current sequence length

    # Final check to compare the last sequence
    max_length = max(max_length, current_length)
    return max_length

# Example usage:
# print(findLengthOfLCIS([1,3,5,4,7]))
← Back to All Questions