动态规划 Leetcode 674 最长连续递增序列

最长连续递增序列

Leetcode 300

学习记录自代码随想录

要点：1.dp[i]定义为nums[i]结尾的连续最长递增蓄力，则正向遍历，递推时，如果是连续序列，则只比较nums[i]和nums[i-1]，若是可以不连续则可以，则需要比较i之前的nums[j]（j = 0:i）与nums[i]的大小。

方法一：dp[i]定义为nums[i]结尾的连续最长递增蓄力，则正向遍历

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        
        int n = nums.size();
        // 1.dp[i]代表以nums[i]结尾的连续递增的子序列
        vector<int> dp(n, 1);
        // 2.递推公式：if(nums[i]>nums[i-1])dp[i] = dp[i-1]+1;连续的所以如果大于的话dp[i-1]+1一定比原来的dp[i]大
        // 3. dp数组初始化为1，最小序列长度为1
        // 4. 遍历顺序：反向遍历
        int result = 1;
        for(int i = 1; i < n; i++){
            if(nums[i] > nums[i-1]) dp[i] = dp[i-1]+1;
            if(dp[i] > result) result = dp[i];
        }
        // 5.举例推导dp数组
        return result;
    }
};

方法二：dp[i]定义为以nums[i]开始的连续最长递增序列，则反向遍历

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        // 1.dp[i]代表以nums[i]开始的连续递增的子序列
        vector<int> dp(n, 1);
        // 2.递推公式：if(nums[i]>nums[i-1])dp[i-1] = max(dp[i-1], dp[i]+1);
        // 3. dp数组初始化为1，最小序列长度为1
        // 4. 遍历顺序：反向遍历
        int result = 1;
        for(int i = n-1; i > 0; i--){
            if(nums[i] > nums[i-1]) dp[i-1] = max(dp[i-1], dp[i]+1);
            if(dp[i-1] > result) result = dp[i-1];
        }
        // 5.举例推导dp数组
        return result;
    }
};