674. Longest Continuous Increasing Subsequence

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

Example 1:

Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3. 
Even though [1,3,5,7] is also an increasing subsequence, it's not a continuous one where 5 and 7 are separated by 4. 

Example 2:

Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1. 

Note: Length of the array will not exceed 10,000.

DP state transition: len[i]代表最長的連續LIS ending with nums[i]的長度 len[i] = 1 if nums[i] <= nums[i - 1] len[i] = len[i - 1] + 1 if nums[i] > nums[i - 1]

int findLengthOfLCIS(vector<int>& nums) { // time: O(n); space: O(n)
    if (nums.empty()) return 0;
    int res = 1, n = nums.size();
    vector<int> len(n, 1); // length of continuous LIS ending with nums[i]
    // DP relation: L[i] = 1 if nums[i] <= nums[i - 1]
    //              L[i] = L[i - 1] + 1 if nums[i] > nums[i - 1]
    for (int i = 1; i < n; ++i) {
        if (nums[i] <= nums[i - 1]) len[i] = 1;
        else len[i] = len[i - 1] + 1;
        res = max(res, len[i]);
    }
    return res;
}

// Space Optimized Dynamic programming
int findLengthOfLCIS(vector<int>& nums) { // time: O(n); space: O(1)
    int res = 0, cur = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (i == 0 || nums[i] <= nums[i - 1]) cur = 1;
        else if (nums[i] > nums[i - 1]) cur += 1;
        res = max(res, cur);
    }
    return res;
}