最长连续递增序列

字数 2214 2025-10-26 12:43:27

最长连续递增序列

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

连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i+1]，那么子序列 [nums[l], nums[l+1], ..., nums[r]] 就是连续递增的。

示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为 3。尽管 [5,4,7] 也是递增的，但它不是连续的，因为 5 和 4 在原数组里不连续。另一个连续的递增序列是 [4,7]，长度为 2。

示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为 1。（注意：序列必须是严格递增的）

解题过程

这个问题要求我们找到一个连续的、严格递增的子数组的最大长度。由于是连续的，我们可以使用线性动态规划，其核心思想是利用前一个位置的状态来推导当前状态。

定义状态
我们定义一个一维数组 dp，其中 dp[i] 表示以第 i 个数字（即 nums[i]）为结尾的连续递增子序列的最大长度。
为什么这么定义？因为一个连续递增序列必然结束于数组中的某个位置。我们求出以每个位置结尾的最长序列，再取最大值，就是整个数组的答案。
状态转移方程
现在我们来思考，如何从已知的状态推导出 dp[i]。
- 如果 nums[i] 比它前一个数字 nums[i-1] 大，那么 nums[i] 可以接在以 nums[i-1] 结尾的连续递增序列后面，形成一个更长的连续递增序列。因此，dp[i] = dp[i-1] + 1。
- 如果 nums[i] 不大于 nums[i-1]，那么它无法接在前面的序列后面。它只能自己作为一个新的序列开头。因此，dp[i] = 1。
将这两种情况合并，我们得到状态转移方程：
dp[i] = (nums[i] > nums[i-1]) ? dp[i-1] + 1 : 1
初始化
根据状态定义，以第一个数字 nums[0] 结尾的连续递增序列长度就是它自己，所以 dp[0] = 1。
确定计算顺序
由于 dp[i] 依赖于 dp[i-1]，我们应该从 i = 1 开始，从左到右（即从前向后）遍历数组。
得到答案
我们的状态 dp[i] 表示的是以 nums[i] 结尾的序列长度。而题目要求的是整个数组中的最大值。因此，答案不是 dp[n-1]，而是 dp 数组中的最大值，即 max(dp[0], dp[1], ..., dp[n-1])。

循序渐进举例

让我们用示例 nums = [1, 3, 5, 4, 7] 来走一遍流程。

初始化：
- 创建 dp 数组，长度与 nums 相同（为5）。
- i = 0：dp[0] = 1。（序列：[1]）
计算 i = 1：
- 比较 nums[1] (3) 和 nums[0] (1)。3 > 1，成立。
- 所以 dp[1] = dp[0] + 1 = 1 + 1 = 2。（序列：[1, 3]）
计算 i = 2：
- 比较 nums[2] (5) 和 nums[1] (3)。5 > 3，成立。
- 所以 dp[2] = dp[1] + 1 = 2 + 1 = 3。（序列：[1, 3, 5]）
计算 i = 3：
- 比较 nums[3] (4) 和 nums[2] (5)。4 > 5？不成立。
- 所以 dp[3] = 1。（序列：[4]）
计算 i = 4：
- 比较 nums[4] (7) 和 nums[3] (4)。7 > 4，成立。
- 所以 dp[4] = dp[3] + 1 = 1 + 1 = 2。（序列：[4, 7]）
得到 dp 数组： [1, 2, 3, 1, 2]
求最大值： max(1, 2, 3, 1, 2) = 3

所以，数组 [1, 3, 5, 4, 7] 的最长连续递增序列的长度是 3。

空间优化
观察状态转移方程，dp[i] 只依赖于 dp[i-1]。我们并不需要保存整个 dp 数组。我们可以用一个变量 currentLength 来记录以当前元素结尾的序列长度，再用一个变量 maxLength 来记录全局最大值。

优化后的代码逻辑如下：

如果数组长度 <= 1，直接返回数组长度。
初始化 maxLength = 1, currentLength = 1。
从 i = 1 开始遍历数组：
- 如果 nums[i] > nums[i-1]，则 currentLength = currentLength + 1，然后更新 maxLength = max(maxLength, currentLength)。
- 否则，currentLength = 1（重新开始计数）。
返回 maxLength。

这种方法将空间复杂度从 O(n) 优化到了 O(1)。

最长连续递增序列题目描述给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[ i] < nums[ i+1]，那么子序列 [ nums[ l], nums[ l+1], ..., nums[ r] ] 就是连续递增的。示例 1：输入：nums = [ 1,3,5,4,7 ] 输出：3 解释：最长连续递增序列是 [ 1,3,5], 长度为 3。尽管 [ 5,4,7] 也是递增的，但它不是连续的，因为 5 和 4 在原数组里不连续。另一个连续的递增序列是 [ 4,7 ]，长度为 2。示例 2：输入：nums = [ 2,2,2,2,2 ] 输出：1 解释：最长连续递增序列是 [ 2 ], 长度为 1。（注意：序列必须是严格递增的）解题过程这个问题要求我们找到一个连续的、严格递增的子数组的最大长度。由于是连续的，我们可以使用线性动态规划，其核心思想是利用前一个位置的状态来推导当前状态。定义状态我们定义一个一维数组 dp ，其中 dp[i] 表示以第 i 个数字（即 nums[i] ）为结尾的连续递增子序列的最大长度。为什么这么定义？因为一个连续递增序列必然结束于数组中的某个位置。我们求出以每个位置结尾的最长序列，再取最大值，就是整个数组的答案。状态转移方程现在我们来思考，如何从已知的状态推导出 dp[i] 。如果 nums[i] 比它前一个数字 nums[i-1] 大，那么 nums[i] 可以接在以 nums[i-1] 结尾的连续递增序列后面，形成一个更长的连续递增序列。因此， dp[i] = dp[i-1] + 1 。如果 nums[i] 不大于 nums[i-1] ，那么它无法接在前面的序列后面。它只能自己作为一个新的序列开头。因此， dp[i] = 1 。将这两种情况合并，我们得到状态转移方程： dp[i] = (nums[i] > nums[i-1]) ? dp[i-1] + 1 : 1 初始化根据状态定义，以第一个数字 nums[0] 结尾的连续递增序列长度就是它自己，所以 dp[0] = 1 。确定计算顺序由于 dp[i] 依赖于 dp[i-1] ，我们应该从 i = 1 开始，从左到右（即从前向后）遍历数组。得到答案我们的状态 dp[i] 表示的是以 nums[i] 结尾的序列长度。而题目要求的是整个数组中的最大值。因此，答案不是 dp[n-1] ，而是 dp 数组中的最大值，即 max(dp[0], dp[1], ..., dp[n-1]) 。循序渐进举例让我们用示例 nums = [1, 3, 5, 4, 7] 来走一遍流程。初始化：创建 dp 数组，长度与 nums 相同（为5）。 i = 0 ： dp[0] = 1 。（序列： [1] ）计算 i = 1 ：比较 nums[1] (3) 和 nums[0] (1) 。 3 > 1 ，成立。所以 dp[1] = dp[0] + 1 = 1 + 1 = 2 。（序列： [1, 3] ）计算 i = 2 ：比较 nums[2] (5) 和 nums[1] (3) 。 5 > 3 ，成立。所以 dp[2] = dp[1] + 1 = 2 + 1 = 3 。（序列： [1, 3, 5] ）计算 i = 3 ：比较 nums[3] (4) 和 nums[2] (5) 。 4 > 5 ？不成立。所以 dp[3] = 1 。（序列： [4] ）计算 i = 4 ：比较 nums[4] (7) 和 nums[3] (4) 。 7 > 4 ，成立。所以 dp[4] = dp[3] + 1 = 1 + 1 = 2 。（序列： [4, 7] ）得到 dp 数组： [1, 2, 3, 1, 2] 求最大值： max(1, 2, 3, 1, 2) = 3 所以，数组 [1, 3, 5, 4, 7] 的最长连续递增序列的长度是 3。空间优化观察状态转移方程， dp[i] 只依赖于 dp[i-1] 。我们并不需要保存整个 dp 数组。我们可以用一个变量 currentLength 来记录以当前元素结尾的序列长度，再用一个变量 maxLength 来记录全局最大值。优化后的代码逻辑如下：如果数组长度 <= 1 ，直接返回数组长度。初始化 maxLength = 1 , currentLength = 1 。从 i = 1 开始遍历数组：如果 nums[i] > nums[i-1] ，则 currentLength = currentLength + 1 ，然后更新 maxLength = max(maxLength, currentLength) 。否则， currentLength = 1 （重新开始计数）。返回 maxLength 。这种方法将空间复杂度从 O(n) 优化到了 O(1)。