Longest Continuous Increasing Subsequence

Patrick Leaton
Published: Feb. 22, 2021, 7:17 p.m.
Problem Description

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

Example 1:

Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. 
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4.

Example 2:

Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.

Note: Length of the array will not exceed 10,000.

 

The description was taken from https://leetcode.com/problems/longest-continuous-increasing-subsequence/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        max_count = count = 1
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                count += 1
            else:
                count = 1
            max_count = max(count, max_count)
        return max_count

Problem Explanation

With problems that require counting a consecutive sequence of the given constraint, like this one and Student Attendance Record I, this can usually be achieved by utilizing a running counter and a maximum counter.

The running counter will increase when the constraint is met, and it will be reset when the constraint is not met.  At the end of each iteration, we will compare the maximum count with the running count to see if we have a new maximum at each point in the traversal.

This algorithm is a precursor to more difficult, sliding window problems, with the only difference being we would increase the window size, the distance between two pointers if the condition was met, and decrease the window size if the condition was not.

First off, if we are given an empty array, then the longest continuous increasing subsequence would be zero.  

        if not nums:
            return 0

 

We will also want to keep track of our maximum increasing subsequence count and our running count, so we will initialize these variables to one since our result would be minimum, a one-index increasing subarray.

        max_count = count = 1

 

We will then traverse the array starting from the second index, checking whether our element is greater than the element behind us.

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

 

If it is, then we're increasing in value, so we'll increment our running count.

                count += 1

 

If not, we're decreasing, so we'll reset our count.  

            else:
                count = 1

 

At the end of each iteration, we'll want to see if our running count is greater than our maximum count.

If it is, the current running count will be saved as the maximum count.

            max_count = max(count, max_count)

 

Once we've traversed the entire array we'll return our max count.  This value will be one if the list had only decreased in values.

        return max_count