Leetcode – Longest Continuous Increasing Subsequence Solution in Python

Spread the love

Introduction

Subsequence problems are ubiquitous in computer science and algorithms. One such problem, known as the “Longest Continuous Increasing Subsequence” (LCIS), appears on Leetcode. This problem is essential for understanding sequence processing and can be solved through various algorithmic approaches. This article will provide an in-depth analysis of the problem, describe the necessary background knowledge, and present different algorithms for solving it using Python.

Problem Statement

Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (subarray).

Example:

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

Output: 3

Explanation: The longest continuous increasing subsequence is [1,3,5], which has a length of 3.

Note:

  • The length of the array will not exceed 10,000.

Solution

1. Simple Iterative Approach

A simple iterative approach is often the first that comes to mind when solving this problem. The key idea here is to keep two counters; one for the length of the current increasing subsequence and another for the maximum length found so far.

  1. Initialize two counters, max_length and current_length, to 1.
  2. Iterate through the input array from index 1 to the end.
  3. For each element, if it is greater than the previous element, increment current_length.
  4. If it is not greater, then compare current_length with max_length and update max_length if necessary. Reset current_length to 1.
  5. After the loop, do one last comparison between current_length and max_length to account for the possibility that the longest continuous increasing subsequence includes the last element.
  6. Return max_length.
def findLengthOfLCIS(nums):
    if not nums:
        return 0
    
    max_length = current_length = 1
    
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            current_length += 1
        else:
            max_length = max(max_length, current_length)
            current_length = 1
    
    return max(max_length, current_length)

Time Complexity:

  • O(n), where n is the length of the input array, since we are iterating through the array once.

Space Complexity:

  • O(1), as we are using a constant amount of extra space.

2. Dynamic Programming (Optional, Not Optimal for this Problem)

Though the dynamic programming approach is not optimal for this particular problem, understanding how it could be applied is valuable for solving more complex variations.

  1. Create an array dp of the same length as the input array, initialized with 1. dp[i] will store the length of the longest continuous increasing subsequence ending at index i.
  2. Iterate through the input array from index 1 to the end.
  3. For each element, if it is greater than the previous element, update dp[i] to be dp[i-1] + 1.
  4. Keep track of the maximum value in the dp array.
  5. Return the maximum value.
def findLengthOfLCIS(nums):
    if not nums:
        return 0
    
    dp = [1] * len(nums)
    max_length = 1
    
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            dp[i] = dp[i-1] + 1
            max_length = max(max_length, dp[i])
    
    return max_length

Time Complexity:

  • O(n), where n is the length of the input array.

Space Complexity:

  • O(n), as we are using an additional array to store the lengths.

Conclusion

The “Longest Continuous Increasing Subsequence” problem is a fundamental sequence processing problem that can be solved through various algorithmic approaches. The simple iterative approach is the most optimal in terms of time and space complexity for this particular problem. However, understanding the dynamic programming approach is also important, especially for more complex variants of subsequence problems.

Leave a Reply