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.
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 ; } }Video 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.