Description
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
Solutions
Solution 1: One-pass Scan
We can traverse the array nums, using a variable cnt to record the length of the current consecutive increasing sequence. Initially, cnt = 1.
Then, we start from index i = 1 and traverse the array nums to the right. Each time we traverse, if nums[i - 1] < nums[i], it means that the current element can be added to the consecutive increasing sequence, so we set cnt = cnt + 1, and then update the answer to ans = max(ans, cnt). Otherwise, it means that the current element cannot be added to the consecutive increasing sequence, so we set cnt = 1.
After the traversal ends, we return the answer ans.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRustPHP
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 ans(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
func findLengthOfLCIS(nums []int) int {
ans, cnt := 1, 1
for i, x := range nums[1:] {
if nums[i] < x {
cnt++
ans = max(ans, cnt)
} else {
cnt = 1
}
}
return ans
}(code-box)
function findLengthOfLCIS(nums: number[]): number {
let [ans, cnt] = [1, 1];
for (let i = 1; i < nums.length; ++i) {
if (nums[i - 1] < nums[i]) {
ans = Math.max(ans, ++cnt);
} else {
cnt = 1;
}
}
return ans;
}(code-box)
impl Solution {
pub fn find_length_of_lcis(nums: Vec<i32>) -> i32 {
let mut ans = 1;
let mut cnt = 1;
for i in 1..nums.len() {
if nums[i - 1] < nums[i] {
ans = ans.max(cnt + 1);
cnt += 1;
} else {
cnt = 1;
}
}
ans
}
}(code-box)
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function findLengthOfLCIS($nums) {
$ans = 1;
$cnt = 1;
for ($i = 1; $i < count($nums); ++$i) {
if ($nums[$i - 1] < $nums[$i]) {
$ans = max($ans, ++$cnt);
} else {
$cnt = 1;
}
}
return $ans;
}
}(code-box)
Solution 2: Two Pointers
We can also use two pointers i and j to find each consecutive increasing sequence, and find the length of the longest consecutive increasing sequence as the answer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRustPHP
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
ans, n = 1, len(nums)
i = 0
while i < n:
j = i + 1
while j < n and nums[j - 1] < nums[j]:
j += 1
ans = max(ans, j - i)
i = j
return ans(code-box)
class Solution {
public int findLengthOfLCIS(int[] nums) {
int ans = 1;
int n = nums.length;
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && nums[j - 1] < nums[j]) {
++j;
}
ans = Math.max(ans, j - i);
i = j;
}
return ans;
}
}(code-box)
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int ans = 1;
int n = nums.size();
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && nums[j - 1] < nums[j]) {
++j;
}
ans = max(ans, j - i);
i = j;
}
return ans;
}
};(code-box)
func findLengthOfLCIS(nums []int) int {
ans := 1
n := len(nums)
for i := 0; i < n; {
j := i + 1
for j < n && nums[j-1] < nums[j] {
j++
}
ans = max(ans, j-i)
i = j
}
return ans
}(code-box)
function findLengthOfLCIS(nums: number[]): number {
let ans = 1;
const n = nums.length;
for (let i = 0; i < n; ) {
let j = i + 1;
while (j < n && nums[j - 1] < nums[j]) {
++j;
}
ans = Math.max(ans, j - i);
i = j;
}
return ans;
}(code-box)
impl Solution {
pub fn find_length_of_lcis(nums: Vec<i32>) -> i32 {
let mut ans = 1;
let n = nums.len();
let mut i = 0;
while i < n {
let mut j = i + 1;
while j < n && nums[j - 1] < nums[j] {
j += 1;
}
ans = ans.max(j - i);
i = j;
}
ans as i32
}
}(code-box)
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function findLengthOfLCIS($nums) {
$ans = 1;
$n = count($nums);
$i = 0;
while ($i < $n) {
$j = $i + 1;
while ($j < $n && $nums[$j - 1] < $nums[$j]) {
$j++;
}
$ans = max($ans, $j - $i);
$i = $j;
}
return $ans;
}
}(code-box)
