Leetcode 674. Longest Continuous Increasing Subsequence

Problem Explanation

The problem requires finding the length of the longest continuous increasing subsequence in an array of integers. A subsequence is defined as a sequence of elements within the array, where each element comes after the previous one.

To use an example for further clarity, if the input array is [1,3,5,4,7], the length of the longest continuous increasing subsequence is 3, since [1,3,5] is the longest subarray that contains continuously increasing elements.

The challenge of the problem lies in the need for the subsequence to be continuous. In the provided example, although [1,3,5,7] is also an increasing subsequence, it's not a continuous one since the numbers 5 and 7 are separated by the number 4.

For the solution, we use an algorithm that loops through the array and keeps track of increasing subsequences. The algorithm then compares the length of each subsequent increasing subsequence with the length of the longest one found so far. If an increasing subsequence is longer, it updates the longest length to be the length of this new subsequence.

To illustrate this, let's illustrate the execution of the algorithm using the example [1,3,5,4,7]:

• Start at index 0 (number 1), this is the start of an increasing subsequence. Continue to the next index.
• At index 1, the numeral (3) is larger than the number at the previous index (1), so we continue.
• Similarly, at index 2, the numeral (5) is larger than the number at the previous index (3), so we continue.
• At index 3, the numeral (4) is not larger than the number at the previous index (5), so we stop here. The subsequence [1,3,5] is increasing and has a length of 3.
• We now continue from index 3, with the numeral 4 marking the start of the next increasing subsequence.

We then implement this logic in various programming languages as per the guidance below.

Python Solution

1
2python
3class Solution:
4    def findLengthOfLCIS(self, nums: List[int]) -> int:
5        ans = 0
6        start = 0
7
8        for i in range(len(nums)):
9            if i and nums[i-1] >= nums[i]: start = i
10            ans = max(ans, i - start + 1)
11        
12        return ans

Java Solution

1
2java
3public class Solution {
4    public int findLengthOfLCIS(int[] nums) {
5        int ans = 0, start = 0;
6        for (int i=0; i<nums.length; ++i) {
7            if (i>0 && nums[i-1] >= nums[i]) start = i;
8            ans = Math.max(ans, i-start+1);
9        }
10        return ans;
11    }
12}

JavaScript Solution

1
2javascript
3var findLengthOfLCIS = function(nums) {
4    let ans = 0, start = 0;
5    
6    for (let i = 0; i < nums.length; i++) {
7        if (i > 0 && nums[i-1] >= nums[i]) start = i;
8        ans = Math.max(ans, i - start + 1);
9    }
10    
11    return ans;
12};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int findLengthOfLCIS(vector<int>& nums) {
6        int res = 0, start = 0;
7        for (int i = 0; i < nums.size(); i++) {
8            if (i > 0 && nums[i-1] >= nums[i]) start = i;
9            res = max(res, i - start + 1);
10        }
11        return res;
12    }
13};

C# Solution

1
2csharp
3public class Solution {
4    public int FindLengthOfLCIS(int[] nums) {
5        int res = 0, start = 0;
6        for (int i = 0; i < nums.Length; ++i) {
7            if (i > 0 && nums[i - 1] >= nums[i]) start = i;
8            res = Math.Max(res, i - start + 1);
9        }
10        return res;
11    }
12}

This problem is solved by keeping two pointers: one to mark the start of the subsequence and one to iterate over the array. At the start, both the pointers point to the first element.

While the iterating pointer points to an element greater than its previous element, we move the pointer to the next element. During this process, we continuously check if the current subsequence is the maximum. If we encounter a number that is not greater than its preceding number, we move the start pointer to this number.

The number of operations in this algorithm is proportional to the size of the array; hence, the time complexity of the solution is O(n), where n is the size of the input array.

This solution does not require any additional space beyond a few variables to keep track of the pointers and the longest sequence's length, so the space complexity is O(1).

No matter the input size, this solution will run efficiently because it uses a linear scanning algorithm. The algorithm is designed only to keep track of the longest increasing sequence without needing to record all ascending sequences within the array, saving both space and time.

Therefore, the problem can be solved efficiently and effectively with different programming languages, including Python, JavaScript, Java, C++, and C#.

Remember that in both programming and problem-solving, understanding the problem's restrictions, in this case, the requirement for the subsequence to be continuous, is key in deriving an effective solution.

Happy coding!