LeetCode-674. 最长连续递增序列-蒲公英云

LeetCode-674. 最长连续递增序列

题目思路

300.最长递增子序列最大的区别在于“连续”。
https://donglin.blog.csdn.net/article/details/129748800

动态规划

1.确定dp数组（dp table）以及下标的含义

dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。
注意这里的定义，一定是以下标i为结尾，并不是说一定以下标0为起始位置。

2.确定递推公式

如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度一定等于以i - 1为结尾的连续递增的子序列长度 + 1 。
即：dp[i] = dp[i - 1] + 1;
本题一层for循环就行，比较nums[i] 和 nums[i - 1]。

3.dp数组如何初始化

以下标i为结尾的连续递增的子序列长度最少也应该是1，即就是nums[i]这一个元素。
所以dp[i]应该初始1;

4.确定遍历顺序

从递推公式上可以看出， dp[i + 1]依赖dp[i]，所以一定是从前向后遍历。

5.举例推导dp数组
已输入nums = [1,3,5,4,7]为例，dp数组状态如下：
在这里插入图片描述
代码实现

class Solution {

public int findLengthOfLCIS(int[] nums) {
    if(nums == null || nums.length == 0){
        return 0;
    }
    int[] dp = new int[nums.length];
    int result = 1;
    for(int i = 0;i<nums.length;i++){
        dp[i] = 1;
    }
    for(int i = 1;i<nums.length;i++){
        if(nums[i]>nums[i-1]){
            dp[i] = dp[i-1]+1;
        }
        result = dp[i] > result?dp[i] : result;
    }
    return result;
}