一、题目描述

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

连续递增的子序列 可以由两个下标 lrl < 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 隔开。 

提示:

  • 1 <= nums.length <= 104
  • -109 <= nums[i] <= 109

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最长连续递增序列( LeetCode 674 ):https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
class Solution {
    public int findLengthOfLCIS(int[] nums) {

        // 设置数组 dp,用来存储 nums 中以每个元素结尾的最长连续递增序列的程度
        // dp[0] 表示以 nums[0] 结尾的最长连续递增序列的长度
        // dp[1] 表示以 nums[1] 结尾的最长连续递增序列的长度
        // dp[i] 表示以 nums[i] 结尾的最长连续递增序列的长度
        int[] dp = new int[nums.length];

        // 首先将数组 dp 里面的值都初始化为 1
        // 1 表示以当前元素结尾的最长连续递增序列的长度为 1
        // 即最长连续递增序列就是当前元素本身
        Arrays.fill(dp, 1);

        // 设置一个变量用来存储最长连续递增序列的结果
        int maxLength = 1;

        // 从 1 开始,直到 dp.length ,往 dp 里面填充结果
        for(int i = 1 ; i < dp.length ; i++){


            // 索引      0  1  2  3  4  5  6
            // nums 为 [ 1, 5, 2, 5, 3, 7, 2 ]
            // 此时 i 为 3,那么 1,5,2 这些数字都在索引位置为 3 的前面
            // 此时发现 i - 1 对应的数字为 2
            // nums[i ] > nums[ i - 1 ],意味着最长连续递增序列的长度增加了
            // 需要更新 dp[i]
            if(nums[i] > nums[ i - 1 ]){
                // 4、更新 dp[i]
                dp[i] = dp[ i - 1] + 1;
            }

            // 在更新 dp[i] 的过程中,发现了一个更长的子序列
            if(maxLength < dp[i]){
                // 那么把更长的子序列的长度赋值给 maxLength
                maxLength = dp[i];
            }
        }

        // 最后返回 maxLength 就行
        return maxLength;
    }
}

2、C++ 代码

3、Python 代码

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注