😄674.最长连续递增子序列

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

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

思路

基本思想

只要当前元素比前一个元素大，那么最长连续递增子序列的长度就可以+1，其余的任何情况，当前元素对应的dp数组中的元素为1，因为破坏了最大连续递增中的连续，所以直接为1，遍历的过程中统计最大的结果即可

对应的判断逻辑为：

1
2
3

if(nuns[i]>nums[i-1]){
    dp[i]=dp[i-1]+1;
}

执行流程

1. 初始化所有的dp数组为1，因为单独的一个元素也算连续递增
2. 按照判断逻辑更新dp数组
3. 统计dp数组中最大的元素，将其当成最终的结果返回

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if(nums.size()==1)
            return 1;
        vector<int> dp(nums.size(),1);
        int res=0;
        for(int i=1;i<nums.size();++i){
            if(nums[i]>nums[i-1]){
                dp[i]=dp[i-1]+1;
            }
            res=max(res,dp[i]);
        }
        return res;
    }
};

总结

相比 300题 求最长递增子序列，本题中增加了连续的条件，使得问题变得简单，一旦前后元素破坏了连续递增的条件，就会回归到最小的递增长度1，一旦前后元素满足连续递增的条件，就会在前一个元素的基础上将系列长度+1

而 300题 是求最长递增子序列，需要在当前元素的前面所有元素中找出比当前元素小的组成递增子序列，所以遇到比当前元素小的元素就可能会更新dp，具体的分析见300题题解