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] <= 109This approach involves iterating through the array while maintaining a variable to track the length of the current continuous increasing subsequence. As we encounter each element, we check if it is larger than the previous one to decide if we should continue the current subsequence or start a new one. We also maintain a global maximum to store the maximum length found during our iteration.
The function findLengthOfLCIS accepts an array and its size. We initialize maxLen and currLen to 1. We iterate through the array, and whenever the current element is greater than the previous one, we increase currLen. If currLen exceeds maxLen, we update maxLen. When the sequence breaks, we reset currLen to 1.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as we use a constant amount of space.
The greedy approach leverages a single pass through the array to determine the maximum length of an increasing subsequence. This method is optimal because it immediately processes each element only once, updating the sequence lengths on the fly, and computing the maximum without revisiting any part of the array.
This code utilizes a greedy solution where it enters the loop with the ability to modify the beginning of sequences implicitly by re-syncing the currLen, ensuring we keep the cost constant per iteration.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as no additional space other than variables is utilized.
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n), where n is the number of elements in the array. |
| Greedy Approach | Time Complexity: O(n), where n is the number of elements in the array. |
Longest Increasing Subsequence - Dynamic Programming - Leetcode 300 • NeetCode • 432,482 views views
Watch 9 more video solutions →Practice Longest Continuous Increasing Subsequence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor