674.最长连续递增序列

题目描述

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。
连续递增的子序列可以由两个下标l和r(l<r)确定，如果对于每个l<=i<r，都有nums[i]<nums[i+1]，那么子序列nums[l],nums[l+1],...,nums[r-1],nums[r]就是连续递增子序列

示例1：

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

示例2：

输入： nums = [2,2,2,2,2]
输出： 1
解释： 最长连续递增序列是[2]，长度为1。

提示

• 1<=nums.length<=10^4
• -10^9<=nums[i]<=10^9

解题思路

1. 确定dp数组的含义
dp[i]为位置i处(包括i)最长的连续递增子序列长度
2. 递推公式
如果nums[i]>nums[i-1]，那么以i为结尾的连续递增子序列的长度为：dp[i-1]+1
3. dp数组初始化
以下标i为结尾的连续递增子序列长度至少为1，故dp[i]=1
4. 确定遍历顺序
从前往后
5. 打印dp数组

代码实现

• 核心模式

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();

        // initialize the DP array
        vector<int> dp(nums.size(), 1);

        int maxLength = 1;
        // traversal 
        for (int i = 1; i < nums.size(); i++){
            if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
            if (dp[i] > maxLength) maxLength = dp[i];
        }

        return maxLength;
    }
};

• ACM模式
dynamicPro.h

#include <iostream>
#include "dynamicPro.h"

class Solution{
public:
    int findLengthOfLCIS(const vector<int>& nums){
        if (nums.size() <= 1) return nums.size();

        // initialize the DP array
        vector<int> dp(nums.size(), 1);

        int maxLength = 1;
        // traversal 
        for (int i = 1; i < nums.size(); i++){
            if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
            if (dp[i] > maxLength) maxLength = dp[i];
        }

        printVector(dp);
        
        return maxLength;
    }
};

int main(){
    vector<int> case1 = {1, 3, 5, 4, 7};
    vector<int> case2 = {2, 2, 2, 2, 2};

    Solution solution;
    cout << "Result1's DP array = " << solution.findLengthOfLCIS(case1) << endl;
    cout << "Result2's DP array = " << solution.findLengthOfLCIS(case2) << endl;

    return 0;
}

• 输出

Result1's DP array = [1, 2, 3, 1, 2]
3
Result2's DP array = [1, 1, 1, 1, 1]
1