LeetCode 674 最长连续递增序列

674.最长连续递增序列

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

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

示例：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

动态规划

本题相较于300.最长递增子序列中，要求序列是连续的，那么对于动态规划数组的定义就需要做出相应的改变。

1. 动态规划数组的定义：定义数组 dp[i] 表示以元素 nums[i] 结尾的最长的连续子序列的长度。

2. 动态规划数组的推导：对于 dp[i] 判断 nums[i]>nums[i-1] ，成立则 dp[i]=dp[i-1]+1 否则 dp[i]=1

3. 动态规划数组的初始化：对于第一个元素 nums[0] 最长的连续序列的长度必然为1，那么 dp[0]=1

4. 动态规划数组的遍历顺序：从前先后遍历

5. 举例验证：对于 nums = [1,3,5,4,7] 动态规划数组的值为：

dp=[1,2,3,1,2]

代码实现：在推导时只需要使用前一个元素的值，使用滚动数组实现

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

贪心实现

基于贪心实现，使用双指针的方式，只需要对数组进行一次遍历。

定义指针 i 直线当前连续递增子序列的第一个元素，指针 j 指向当前递增子序列的最后一个元素。初始时 i==j ，指针 j 后移一位，若是 nums[j]>nums[j+1] 那么 j++ ，否则 len=j-i,res=max(res,len) ，然后 i=j 继续循环。

代码实现：

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