数据结构与算法之动态规划: LeetCode 674. 最长连续递增序列 (Ts版)

最长连续递增序列

• https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/

描述

• 给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度
• 连续递增的子序列 可以由两个下标 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 <= $10^4$
• -$10^9$ <= nums[i] <= $10^9$

Typescript 版算法实现

1 ) 方案1: 贪心

function findLengthOfLCIS(nums: number[]): number {const n = nums.length;if (n <= 1) return n;let start = 0;let ans = 0;for (let i = 0; i < n; i++) {if (i > 0 && nums[i] <= nums[i - 1]) {start = i;}ans = Math.max(ans, i - start + 1);}return ans;
};

2 ) 方案2: 贪心变体

function findLengthOfLCIS(nums: number[]): number {const n = nums.length;if (n <= 1) return n;let count = 1;let ans = 1;for (let i = 0; i < n - 1; i++) {nums[i + 1] > nums[i] ? count ++ : (count = 1);ans = Math.max(ans, count);}return ans;
};

3 ) 方案3: 动态规划

function findLengthOfLCIS(nums: number[]): number {// 获取长度const n = nums.length;if (n <= 1) return n;// 定义记录结果的变量let count: number = 0;// 定义dp数组并初始化为1let dp: number[] = new Array(n).fill(1);// 遍历for (let i = 1; i < n; i++) {if (nums[i - 1] < nums[i]) {// 状态转移方程: 不连续递增子序列的跟前 0-i 个状态有关，连续递增的子序列只跟前一个状态有关dp[i] = dp[i - 1] + 1;}// 记录dp数组中的最大值if (count < dp[i]) count = dp[i];}return count;
}