EasyArraysSliding Window

Longest Continuous Increasing Subsequence

1 approach, code in every language

Given an integer array, find the length of the longest run of elements that is strictly increasing and unbroken, meaning the chosen elements must sit next to each other in the original order. Ties in value break the streak, so equal neighbours cannot be part of the same run.

You can think of it as a window that keeps growing while each new element is larger than the one before it, and collapses back to size one the instant that rule is violated.

Example 1

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

Output: 3

The run 1,3,5 climbs for three elements before 4 breaks the streak; 4,7 only reaches length two.

Example 2

Input: nums = [2,2,2,2]

Output: 1

No neighbour is strictly larger than the previous one, so the longest strictly increasing run is a single element.

Constraints

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

Running window with reset

Track the length of the current increasing run, extending it when the next element is larger and resetting it to one otherwise.

Loading animation…

Intuition

Because the run must be contiguous, you never need to look back further than the immediately previous element. As long as each new value is bigger than its predecessor, the current window simply grows by one. The first time that ordering fails, the window can no longer include the earlier elements, so it restarts at the current position. Keep a running maximum of the window length as you go.

Algorithm walkthrough

1Handle the empty array by returning 0, then set both the best length and the current length to 1.
2Walk from the second element to the end of the array.
3If the current element is strictly greater than the previous one, extend the current length and refresh the best length.
4Otherwise the streak is broken, so reset the current length back to 1.
5After the sweep, the best length holds the answer.

Implementation

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

Time

O(n)

Space

O(1)

A single pass with a couple of counters covers the whole array.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Longest Rising Run of Gauge Readings is our own problem on the technique behind Longest Continuous Increasing Subsequence: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free