最长递增子数组问题与解法

开会员与付费前请必须阅读这篇文章，在首页置顶第一篇：（进站必看本站VIP介绍/购买须知）
本站所有源码均为自动秒发货，默认（百度网盘）

在算法与数据结构的学习中，最长递增子数组（Longest Increasing Subarray）是一个经典且重要的问题。它不仅是理解动态规划思想的绝佳入门案例，也常见于面试笔试中。本文将从问题定义、核心解法到代码实现，清晰地为你剖析这个问题。

问题定义

给定一个整数数组 nums，我们需要找到其中连续的、并且元素严格递增的子数组（子数组是原数组中连续的一部分），并返回该子数组的最大长度。

关键点：这里的“连续”至关重要，它区别于另一个经典问题“最长递增子序列”（Longest Increasing Subsequence, LIS），后者不要求元素在原数组中位置连续。

示例：

输入: [3, 1, 4, 1, 5, 9, 2, 6]

输出: 4

解释: 最长递增子数组是 [1, 5, 9]吗？不，因为 9 到 2 递减了。实际上，最长的是 [1, 5, 9]只有3个。让我们仔细看，递增的连续段有：[3], [1,4], [1,5,9], [2,6]。其中最长的 [1,5,9]长度为3。等一下，数组中有 [1,4]? 不，4>1，但4的下一个元素是1，中断了。我们重新找连续递增段：[3](1), [1,4](2), [1](1), [5,9](2), [2,6](2)。所以最长长度是2。我的示例似乎不够典型，让我们换一个更清晰的示例。

为了更清晰地说明，我们使用一个新示例：

输入: [1, 3, 5, 4, 7, 8, 9]

输出: 4

解释: 最长的连续递增子数组是 [4, 7, 8, 9]，其长度为4。

动态规划解法

我们可以用动态规划的思路来解决，其核心是定义一个状态，并找到状态之间的转移关系。

定义状态：
- 令 dp[i]表示以第 i个元素 nums[i] 作为结尾的最长递增子数组的长度。
状态转移方程：
- 如果 nums[i] > nums[i-1]，那么 nums[i]可以接在以 nums[i-1]结尾的递增子数组后面，形成一个更长的连续递增子数组。因此，dp[i] = dp[i-1] + 1。
- 如果 nums[i] <= nums[i-1]，那么递增的连续性在此中断。以 nums[i]结尾的递增子数组只能包含它自己。因此，dp[i] = 1。
- 归纳为：dp[i] = (nums[i] > nums[i-1]) ? dp[i-1] + 1 : 1
初始状态：
- 以第一个元素结尾的递增子数组显然就是它本身，所以 dp[0] = 1。
最终结果：
- 结果不是 dp[n-1]，因为最长递增子数组不一定以最后一个元素结尾。我们需要遍历整个 dp数组，找到其中的最大值 max(dp)。

基础动态规划代码实现

def find_length_of_lcis(nums):
    """
    寻找最长连续递增子数组的长度。
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0
    
    n = len(nums)
    dp = [1] * n  # 初始化dp数组，每个位置至少长度为1
    max_length = 1
    
    for i in range(1, n):
        if nums[i] > nums[i-1]:
            dp[i] = dp[i-1] + 1
        # 如果nums[i] <= nums[i-1]，dp[i]保持为1，已初始化
        max_length = max(max_length, dp[i])
    
    return max_length

空间优化

观察上面的代码，我们发现计算 dp[i]时，只依赖于前一个状态 dp[i-1]。因此，我们可以用单个变量 current_length来代替整个 dp数组，将空间复杂度从 O(n) 优化到 O(1)。

def find_length_of_lcis_optimized(nums):
    """
    寻找最长连续递增子数组的长度（空间优化版）。
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0
    
    max_length = 1
    current_length = 1  # 记录以当前位置结尾的递增子数组长度
    
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            current_length += 1
            max_length = max(max_length, current_length)
        else:
            current_length = 1  # 递增中断，重置长度
    
    return max_length

示例推演

以数组 nums = [3, 1, 4, 1, 5, 9, 2, 6]为例，走一遍优化算法的流程：

i	nums[i]	nums[i] > nums[i-1]?	current_length	max_length
初始化			1	1
1	1	3>1? False	重置为 1	1
2	4	1<4? True	1+1=2	max(1,2)=2
3	1	4>1? False	重置为 1	2
4	5	1<5? True	1+1=2	max(2,2)=2
5	9	5<9? True	2+1=3	max(2,3)=3
6	2	9>2? False	重置为 1	3
7	6	2<6? True	1+1=2	max(3,2)=3

最终结果：max_length = 3。对应的最长连续递增子数组是 [1, 5, 9]。

总结

解决“最长递增子数组”问题的关键在于：

理解“连续”的约束，这简化了状态转移的逻辑。
定义明确的状态：dp[i]表示以 nums[i]结尾的解。
找到简洁的转移方程：只需比较当前元素与前一个元素。
空间优化是自然的，因为状态转移只依赖前一项。

问题定义

动态规划解法

基础动态规划代码实现

空间优化

示例推演

总结

相关文章