674.longest-continuous-increasing-subsequence.md

674. Longest Continuous Increasing Subsequence

This problem is asking the longest increasing "subarray".

Hints

• Try to use two pointers or a sliding window to track the current increasing subarray.
• What should you do when the sequence is no longer increasing?

Breakdowns

1. How do you identify the start and end of a continuous increasing subarray?

Keep a pointer to the start of the current increasing sequence. When the next number is not greater than the previous, reset the start.

2. How do you efficiently find the longest such subarray?

Iterate through the array, updating the maximum length whenever the sequence continues, and resetting when it breaks.

Key Insights

• This is a classic sliding window/two pointers problem where the window expands as long as the sequence is strictly increasing.
• Reset the window whenever the sequence is not increasing.
• Greedy and two pointers both work efficiently for this problem.

Test Cases

Normal Cases

Input: nums = [1,2,5,3,4,5,6]
Output: 4

Input: nums = [1,2,5,6,3,4,5]
Output: 4

Edge / Corner Cases

• All elements are equal:

Input: nums = [1,1,1,1,1,1,1]
Output: 1

• All elements are decreasing:

Input: nums = [7,6,5,4,3,2,1]
Output: 1

Straightforward (Greedy)

• Track the current length of the increasing subarray.

1. If the current number is greater than previous, then increase the length and update the max length.
2. Else, reset the length.

fun findLengthOfLCIS(nums: IntArray): Int {
    var ans = 1
    var len = 1
    for (i in 1 until nums.size) {
        if (nums[i - 1] < nums[i]) {
            len++
        } else {
            len = 1
        }
        ans = maxOf(ans, len)
    }
    return ans
}

Two Pointers (Group by Consecutive)

fun findLengthOfLCIS(nums: IntArray): Int {
    var ans = 0
    var i = 0
    while (i < nums.size) {
        val start = i
        i++
        while (i < nums.size && nums[i - 1] < nums[i]) {
            i++
        }
        ans = maxOf(ans, i - start)
    }
    return ans
}

Edge Cases

• All elements are the same: The answer is 1, since no increasing sequence exists.
• All elements are strictly decreasing: The answer is 1, for the same reason.
• The longest increasing sequence is at the start or end of the array.
• Array of length 1: The answer is 1.

Pitfalls

• Forgetting to reset the current length or start pointer when the sequence breaks.
• Off-by-one errors when calculating the length of the current window (should be end - start + 1 or i - start).
• Not handling arrays of length 0 or 1 correctly.