674. Longest Continuous Increasing Subsequence

Edited by Charles

Easy · Python · Dynamic Programming

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Given an integer array nums, find the length of the Longest Continuous Increasing Subsequence (LCIS).

Unlike Longest Increasing Subsequence (LIS), the elements in LCIS must be contiguous.

Original study notes follow, including intermediate snippets and earlier attempts.

Idea

Given an integer array nums, find the length of the Longest Continuous Increasing Subsequence (LCIS).

Unlike Longest Increasing Subsequence (LIS), the elements in LCIS must be contiguous.

For example:

nums = [1,3,5,4,7]

The longest continuous increasing subsequence is:

[1,3,5]

Its length is 3.

Dynamic Programming

State Definition

Let

dp[i]

denote:

The length of the longest continuous increasing subsequence ending at nums[i].

Since the subsequence must be continuous, the previous element can only be nums[i-1].

For example:

nums = [1,3,5,4,7]

Then

dp[0] = 1    # [1]
dp[1] = 2    # [1,3]
dp[2] = 3    # [1,3,5]
dp[3] = 1    # [4]
dp[4] = 2    # [4,7]

Initialization

Each element itself forms a continuous increasing subsequence of length 1.

Therefore,

dp = [1] * len(nums)

That is,

dp[i] = 1

State Transition

Since the subsequence must be continuous, we only need to compare the current element with its immediate previous element.

If

nums[i] > nums[i - 1]

then nums[i] can extend the previous continuous increasing subsequence.

Update:

dp[i] = dp[i - 1] + 1

Otherwise,

dp[i] = 1

since a new subsequence starts at nums[i].

Transition equation:

if nums[i] > nums[i - 1]:
    dp[i] = dp[i - 1] + 1
else:
    dp[i] = 1

The key observation is that continuity removes the need to examine all previous elements.

Why Do We Need a Global Maximum?

The longest continuous increasing subsequence does not necessarily end at the last element.

For example,

nums = [1,2,3,0]

Then

dp = [1,2,3,1]

The answer is

3

instead of

dp[-1] = 1

Therefore, we maintain a variable res to record the maximum value throughout the traversal.

Example

nums = [1,3,5,4,7]

Initialization:

nums = [1,3,5,4,7]
dp   = [1,1,1,1,1]

i = 1, nums[1] = 3

3 > 1

Extend the previous subsequence:

dp = [1,2,1,1,1]

i = 2, nums[2] = 5

5 > 3

Continue extending:

dp = [1,2,3,1,1]

i = 3, nums[3] = 4

4 > 5   False

The increasing sequence is broken.

Start a new subsequence:

dp = [1,2,3,1,1]

i = 4, nums[4] = 7

7 > 4

Extend the new subsequence:

dp = [1,2,3,1,2]

Final answer:

3

Complexity Analysis

Time Complexity

O(n)

Each element is visited exactly once.

Space Complexity

O(n)

A DP array of length n is used.

Note: Since dp[i] only depends on dp[i-1], the space complexity can be optimized to O(1) by keeping only the current length.

Summary

State Definition

dp[i] = length of the longest continuous increasing subsequence ending at nums[i]

Initialization

dp = [1] * len(nums)

State Transition

if nums[i] > nums[i - 1]:
    dp[i] = dp[i - 1] + 1
else:
    dp[i] = 1

Traversal Order

Traverse the array from left to right, comparing each element with its immediate predecessor.

Final Answer

max(dp)

or maintain a running maximum during traversal.

Common Mistakes

1. This problem asks for a continuous increasing subsequence, so elements must be adjacent.
2. Unlike LeetCode 300 (Longest Increasing Subsequence), there is no need to iterate through all previous elements. Only compare nums[i] with nums[i - 1].
3. Do not return dp[-1], since the longest continuous increasing subsequence does not necessarily end at the last element.
4. The sequence must be strictly increasing, so the condition should be

nums[i] > nums[i - 1]

instead of

nums[i] >= nums[i - 1]

Study record

Field	Value
Attempts	1
Mastery	❚

Python solution

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        l = len(nums)

        dp = [1] * l
        res = 1

        for i in range(1, l):
            if nums[i] > nums[i - 1]:
                dp[i] = dp[i - 1] + 1
            res = max(res, dp[i])

        return res

---

Back to Day 37 Dynamic Programming X · All Algorithm notes