【leetcode】674. 最长连续递增序列（longest-continuous-increasing-subsequence）（DP）[简单]

链接

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

耗时

解题：57 min
题解：21 min

题意

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

思路

dp[i] 表示数组的长度为 i 并且以nums[i-1]为结尾的最长且连续递增的子序列的长度。唯一需要注意的是：初始化的时候可能存在数组为空的情况，所以 dp[0] 应初始化为 0。

状态转移方程：
d p [ i ] = { d p [ i − 1 ] + 1    ( n u m s [ i ] > n u m s [ i − 1 ] ) 1    ( 其 它 ) dp[i] = \begin{cases} dp[i-1]+1 \ \ (nums[i]>nums[i-1]) \\ 1 \ \ (其它) \end{cases} dp[i]={dp[i−1]+1  (nums[i]>nums[i−1])1  (其它)​

答案即是 dp[] 中的最大值。

时间复杂度： O ( n ) O(n) O(n)

PS：因为每个 dp[i] 只与前一项 dp[i-1] 有关，所以可以使用一个变量代替 dp[]。下面的代码即是空间优化后的实现。

AC代码

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        int ans = min(1, n), tmp = 1;
        for(int i = 1; i < n; ++i) {
            if(nums[i] > nums[i-1]) {
                tmp += 1;
                ans = max(ans, tmp);
            }
            else {
                tmp = 1;
            }
        }
        return ans;
    }
};