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

左手的ㄟ右手 2024-03-26 21:35 63阅读 0赞

#### 目录 ####

*   *  题目思路
     *  动态规划

题目来源  
[674. 最长连续递增序列][674.]

### 题目思路 ###

300.最长递增子序列最大的区别在于“连续”。  
[https://donglin.blog.csdn.net/article/details/129748800][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数组状态如下：  
    ![在这里插入图片描述][69c04205bb804ac8aa43ecff3ad20199.png]  
    代码实现

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;
        }
    }

![在这里插入图片描述][752fcd32b50f43e4a7b47fee77516429.png]

[674.]: https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
[https_donglin.blog.csdn.net_article_details_129748800]: https://donglin.blog.csdn.net/article/details/129748800
[69c04205bb804ac8aa43ecff3ad20199.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/afd1b175bfcd40d586061f7cff5ef9b7.png
[752fcd32b50f43e4a7b47fee77516429.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/5cc5d163b3454565b168ca3a15c43e28.png