674. Longest Continuous Increasing Subsequence

Question

LeetCode Problem

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 <= 10^4
• -10^9 <= nums[i] <= 10^9

Solutions

Use dynamic programming.

• dp 定義：dp[i] 是 nums[i] 的最長連續遞增序列
• 遞推公式：if (nums[i-1] < nums[i]) dp[i] = dp[i-1] + 1

Time Complexity: O(N)
Space Complexity: O(N)

int findLengthOfLCIS(vector<int>& nums) {
	int m = static_cast<int>(nums.size());
	if (m <= 1) return m;
	vector<int> dp(m, 1);
	int maxLen = 1;
	for (int i = 1; i < m; ++i) {
		if (nums[i] > nums[i-1]) {
			dp[i] = dp[i-1] + 1;
		}
		maxLen = max(maxLen, dp[i]);
	}
	return maxLen;
}

An Optimal Method for Space Complexity

Time Complexity: O(N)
Space Complexity: O(1)

int findLengthOfLCIS(vector<int>& nums) {
	int m = static_cast<int>(nums.size());
	int curLen = 1;
	int maxLen = 1;
	for (int i = 0; i < m; ++i) {
		if (nums[i - 1] < nums[i]) {
			++curLen;
		} else {
			--curLen;
		}
		maxLen = max(maxLen, curLen);
	}
	return maxLen;
}