【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)。