Longest Continuous Increasing Subsequence
EasyPrompt
Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.
A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].
Example 1:
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 an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.Example 2:
Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly
increasing.
Constraints:
1 <= nums.length <= 104-109 <= nums[i] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible continuous subarray to see if it is strictly increasing. We keep track of the length of the longest valid subarray found.
Algorithm
- Handle the edge case of an empty array by returning 0. If the array is not empty, initialize
maxLengthto 1, as a single element is a valid subsequence. - Use an outer loop with index
ifrom0ton-1to iterate through all possible starting points of a subarray. - For each
i, use an inner loop with indexjfromi+1ton-1to extend the subarray. - Inside the inner loop, check if
nums[j] > nums[j-1]. - If the condition is true, it means the subsequence is still increasing. Calculate the current length
j - i + 1and updatemaxLength = Math.max(maxLength, j - i + 1). - If the condition is false, the continuous increasing sequence is broken. Break the inner loop and proceed to the next starting point
i. - After the loops complete, return
maxLength.
Walkthrough
The core idea is to generate all subarrays and validate them. We use a nested loop structure. The outer loop, indexed by i, determines the starting element of a potential continuous increasing subsequence. The inner loop, indexed by j, extends the subarray from i to j. For each extension, we check if the newly added element nums[j] is strictly greater than the previous element nums[j-1]. If it is, we have a valid continuous increasing subsequence of length j - i + 1, and we update our maxLength if this length is greater. If nums[j] <= nums[j-1], the increasing property is violated, so we can stop extending the subarray from i and break the inner loop, moving to the next starting point i+1.
class Solution { public int findLengthOfLCIS(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int maxLength = 1; for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] > nums[j - 1]) { maxLength = Math.max(maxLength, j - i + 1); } else { break; } } } return maxLength; }}Complexity
Time
O(n^2), where n is the number of elements in `nums`. In the worst-case scenario (a sorted array), the inner loop runs approximately `n-i` times for each `i`, leading to a total of roughly n^2/2 operations.
Space
O(1), as we only use a few variables (`maxLength`, `i`, `j`) to store state, regardless of the input size.
Trade-offs
Pros
Conceptually simple and easy to implement.
Cons
Inefficient for large arrays due to its quadratic time complexity, which will likely result in a 'Time Limit Exceeded' error on online judges for larger constraints.
A much more efficient solution is to iterate through the array a single time. We can maintain a count of the length of the current continuous increasing subsequence and update a global maximum length whenever this sequence breaks or the array traversal ends.
Algorithm
- Handle the edge case where the input array
numsis null or empty by returning 0. - Initialize
maxLength = 1andcurrentLength = 1. This handles non-empty arrays, as the minimum possible answer is 1. - Iterate through the array from the second element (
i = 1) to the end. - In each iteration, compare the current element
nums[i]with the previous elementnums[i-1]. - If
nums[i] > nums[i-1], the current increasing subsequence continues, so incrementcurrentLength. - Otherwise, the subsequence is broken. Update
maxLengthwith the maximum of its current value andcurrentLength. Then, resetcurrentLengthto 1. - After the loop completes, the last subsequence's length is still in
currentLength. Perform one final update:maxLength = Math.max(maxLength, currentLength). - Return
maxLength.
Walkthrough
This approach can be thought of as a sliding window. The window expands as long as we find increasing elements and resets when the condition is not met. We use two variables: maxLength to store the overall maximum length found, and currentLength for the length of the window (the current subsequence).
We iterate through the array starting from the second element (i=1). We compare nums[i] with nums[i-1]:
- If
nums[i] > nums[i-1], the sequence continues. We incrementcurrentLength. - If
nums[i] <= nums[i-1], the sequence is broken. Before resetting, we must check if the sequence that just ended is the longest one seen so far by updatingmaxLength = Math.max(maxLength, currentLength). Then, we resetcurrentLengthto 1, as the current elementnums[i]starts a new potential subsequence of length 1.
After the loop finishes, it's possible the longest subsequence is the one at the very end of the array (e.g., [1,2,3,4,5]). In this case, the maxLength would not have been updated for this final sequence. Therefore, a final comparison maxLength = Math.max(maxLength, currentLength) is necessary before returning the result.
class Solution { public int findLengthOfLCIS(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int maxLength = 1; int currentLength = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] > nums[i - 1]) { currentLength++; } else { maxLength = Math.max(maxLength, currentLength); currentLength = 1; } } // Final check for the case where the longest subsequence is at the end return Math.max(maxLength, currentLength); }}Complexity
Time
O(n), where n is the number of elements in `nums`. We perform a single pass through the array.
Space
O(1), as we only use a constant number of variables (`maxLength`, `currentLength`, `i`) for our calculations.
Trade-offs
Pros
Optimal time efficiency with a linear time complexity.
Space efficient, using only constant extra space.
Cons
Requires careful handling of the final update after the loop to account for subsequences that extend to the end of the array.
Solutions
Solution
class Solution { public int findLengthOfLCIS ( int [] nums ) { int ans = 1 ; for ( int i = 1 , cnt = 1 ; i < nums . length ; ++ i ) { if ( nums [ i - 1 ] < nums [ i ]) { ans = Math . max ( ans , ++ cnt ); } else { cnt = 1 ; } } return ans ; } }class Solution { public: int findLengthOfLCIS ( vector < int >& nums ) { int ans = 1 ; for ( int i = 1 , cnt = 1 ; i < nums . size (); ++ i ) { if ( nums [ i - 1 ] < nums [ i ]) { ans = max ( ans , ++ cnt ); } else { cnt = 1 ; } } return ans ; } };class Solution : def findLengthOfLCIS ( self , nums : List [ int ]) -> int : ans = cnt = 1 for i , x in enumerate ( nums [ 1 :]): if nums [ i ] < x : cnt += 1 ans = max ( ans , cnt ) else : cnt = 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.