【LeetCode】674. 最长连续递增序列（简单）——代码随想录算法训练营Day52

题目链接：

题目描述

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

连续递增的子序列 可以由两个下标 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 <= 104
• -109 <= nums[i] <= 109

文章讲解：代码随想录

视频讲解：动态规划之子序列问题，重点在于连续！| LeetCode：674.最长连续递增序列_哔哩哔哩_bilibili

题解1：贪心算法

思路：取更长的连续子序列为局部最优，全局最优为最长连续子序列。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
    let res = 1;
    let temp = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            temp++;
            if (temp > res) {
                res = temp;
            }
        } else {
            temp = 1;
        }
    }
    return res;
};

分析：时间复杂度为 O(n)，空间复杂度为 O(1)。

题解2：动态规划

思路：使用动态规划法求解子序列问题。

动态规划分析：

• dp 数组以及下标的含义：dp[i] 代表以 nums[i] 结尾的最长递增子序列的长度。
• 递推公式：nums[i] 大于 nums[i - 1] 时，dp[i] = dp[i - 1] + 1。
• dp 数组初始化：全部初始化为1。
• 遍历顺序：从前到后。
• 打印 dp 数组：以输入 [1,3,5,4,7] 为例，dp 数组为 [ 1, 2, 3, 1, 2 ]。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findLengthOfLCIS = function(nums) {
    const dp = new Array(nums.length).fill(1);
    for (let i = 1; i < nums.length; i++) {
        dp[i] = nums[i] > nums[i - 1] ? dp[i - 1] + 1 : 1;
    }
    return Math.max(...dp);
};

分析：时间复杂度为 O()，空间复杂度为 O()。

收获

练习动态规划法求解子序列问题，注意本题为连续子序列。