LeetCode 674: Longest Continuous Increasing Subsequence

Problem Restatement

We are given an unsorted integer array nums.

We need to return the length of the longest continuous increasing subsequence.

Here, continuous means the elements must be adjacent in the original array. So this is really asking for the longest strictly increasing subarray. The official statement defines it as a continuous subarray where each next element is strictly greater than the previous one.

Input and Output

Example function shape:

def findLengthOfLCIS(nums: list[int]) -> int:
    ...

Examples

Consider:

nums = [1, 3, 5, 4, 7]

The longest continuous increasing subsequence is:

1, 3, 5

Its length is:

3

Even though:

1, 3, 5, 7

is an increasing subsequence, it is not continuous because 5 and 7 are separated by 4.

So the answer is:

3

Another example:

nums = [2, 2, 2, 2, 2]

The sequence must be strictly increasing.

Equal values do not continue the run.

So the longest continuous increasing subsequence has length:

1

First Thought: Check Every Subarray

A direct solution is to try every subarray and check whether it is strictly increasing.

For each starting index, we can extend right while the values keep increasing.

This works, but it repeats work.

If the array has length n, checking all subarrays can take:

O(n^2)

We can do better because an increasing run can be tracked while scanning once.

Key Insight

A continuous increasing subsequence only depends on adjacent comparisons.

When we are at index i, there are two cases:

1. If nums[i] > nums[i - 1], the current increasing run continues.
2. Otherwise, the current run breaks and must restart at nums[i].

So we only need two variables:

Algorithm

1. If nums is empty, return 0.
2. Set current = 1.
3. Set answer = 1.
4. Scan from index 1 to the end.
5. If nums[i] > nums[i - 1], increase current.
6. Otherwise, reset current to 1.
7. Update answer.
8. Return answer.

Correctness

At every index i, current stores the length of the longest continuous strictly increasing subarray that ends at i.

If nums[i] > nums[i - 1], then any increasing run ending at i - 1 can be extended by nums[i], so current increases by 1.

If nums[i] <= nums[i - 1], then no continuous increasing subarray ending at i can include nums[i - 1], so the best run ending at i has length 1.

The variable answer is updated after every index, so it stores the maximum length among all increasing runs seen so far.

Therefore, after the scan finishes, answer is exactly the length of the longest continuous increasing subsequence.

Complexity

Implementation

from typing import List

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if not nums:
            return 0

        current = 1
        answer = 1

        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                current += 1
            else:
                current = 1

            answer = max(answer, current)

        return answer

Code Explanation

We handle an empty array first:

if not nums:
    return 0

Then we initialize both counters to 1:

current = 1
answer = 1

A single element is always a valid continuous increasing subsequence.

We scan from the second element:

for i in range(1, len(nums)):

If the current value is greater than the previous value, the run continues:

if nums[i] > nums[i - 1]:
    current += 1

Otherwise, the run breaks:

else:
    current = 1

After each step, update the best length:

answer = max(answer, current)

Finally, return the best run length.

Testing

def run_tests():
    s = Solution()

    assert s.findLengthOfLCIS([1, 3, 5, 4, 7]) == 3
    assert s.findLengthOfLCIS([2, 2, 2, 2, 2]) == 1

    assert s.findLengthOfLCIS([1, 2, 3, 4, 5]) == 5
    assert s.findLengthOfLCIS([5, 4, 3, 2, 1]) == 1

    assert s.findLengthOfLCIS([1]) == 1
    assert s.findLengthOfLCIS([]) == 0

    assert s.findLengthOfLCIS([1, 3, 5, 7, 2, 4, 6, 8]) == 4

    print("all tests passed")

run_tests()

Test meaning: