Longest Continuous Increasing Subsequence — Solution
Longest Continuous Increasing Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Longest Continuous Increasing Subsequence is an easy coding problem on arrays, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an unsorted integer array nums. Return the length of the longest continuous strictly increasing run — a subarray nums[l..r] in which every element is strictly greater than the one before it.
Example 1
Input: nums = [2,6,8,3,4,5,9,1]
Output: 4
Explanation: The run `[3,4,5,9]` has length 4; `[2,6,8]` has only 3.
Example 2
Input: nums = [5,5,5]
Output: 1
Explanation: Equal neighbours break a strictly increasing run, so each run is a single element.
Example 3
Input: nums = [-3,-1,0,7]
Output: 4
Constraints
1 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9
Hints for Longest Continuous Increasing Subsequence
Hint 1
A run ends exactly where
nums[i] <= nums[i - 1].Hint 2
Scan once, keeping the length of the run that ends at the current index: extend it when the element increases, reset it to 1 otherwise.
How to solve Longest Continuous Increasing Subsequence
Maximal increasing runs are separated by the positions where the sequence fails to increase, so one pass that tracks the current run length finds the longest.
Approach
- Set
cur = 1andbest = 1. - For
ifrom 1 ton - 1: ifnums[i] > nums[i - 1], incrementcur; otherwise resetcur = 1. - Update
best = max(best, cur)after each step and return it.
Why it works
cur is always the length of the longest strictly increasing subarray ending at index i: either it extends the run ending at i - 1, or the comparison fails and only nums[i] itself remains. The answer is the maximum of these lengths over all end points.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Strictly increasing: equal neighbours end a run.
- This is about contiguous runs, not the longest increasing subsequence (which may skip elements).
Reference solution
Python
from typing import List
def findLengthOfLCIS(nums: List[int]) -> int:
best = cur = 1
for i in range(1, len(nums)):
cur = cur + 1 if nums[i] > nums[i - 1] else 1
best = max(best, cur)
return bestJava
public static int findLengthOfLCIS(int[] nums) {
int best = 1, cur = 1;
for (int i = 1; i < nums.length; i++) {
cur = nums[i] > nums[i - 1] ? cur + 1 : 1;
best = Math.max(best, cur);
}
return best;
}C++
int findLengthOfLCIS(vector<int>& nums) {
int best = 1, cur = 1;
for (int i = 1; i < (int)nums.size(); i++) {
cur = nums[i] > nums[i - 1] ? cur + 1 : 1;
best = max(best, cur);
}
return best;
}JavaScript
var findLengthOfLCIS = function(nums) {
var best = 1, cur = 1;
for (var i = 1; i < nums.length; i++) {
cur = nums[i] > nums[i - 1] ? cur + 1 : 1;
if (cur > best) best = cur;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays