【Leetcode】674. Longest Continuous Increasing Subsequence

題目位址：

https://leetcode.com/problems/longest-continuous-increasing-subsequence/

給定一個數組，求其最長連續上升子序列的長度。可以應用動态規劃思想。設 f [ i ] f[i] f[i]為以 n u m s [ i ] nums[i] nums[i]結尾的最長的連續上升子序列的長度。那麼這個子序列有兩種情況：

1、如果 n u m s [ i ] > n u m s [ i − 1 ] nums[i]>nums[i-1] nums[i]>nums[i−1]，那麼就可以把 n u m s [ i ] nums[i] nums[i]接上以 n u m s [ i − 1 ] nums[i-1] nums[i−1]結尾的子序列構成更長的子序列，這個子序列必然是以 n u m s [ i ] nums[i] nums[i]結尾的最長上升子序列，此時 f [ i ] = f [ i − 1 ] + 1 f[i]=f[i-1]+1 f[i]=f[i−1]+1；

2、否則， f [ i ] = 1 f[i]=1 f[i]=1。

最後結果就是 f f f數組中的最大值。代碼如下：

public class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // cur存儲的是以目前數字結尾的最長上升子序列的長度，
        // res存儲的是最終結果
        int cur = 1, res = 1;
        for (int i = 1; i < nums.length; i++) {
        	// 如果能與前一個數字接上，就加1，否則就重置為1
            if (nums[i] > nums[i - 1]) {
                cur++;
            } else {
                cur = 1;
            }
            // res要儲存目前已知的最大值
            res = Math.max(res, cur);
        }
        
        return res;
    }
}
           

時間複雜度 O ( n ) O(n) O(n)，空間 O ( 1 ) O(1) O(1)。