最大子数组和

1.题目(leetcode53)

给你一个整数数组$nums$，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2

输入：nums = [1] 输出：1

示例 3

输入：nums = [5,4,-1,7,8] 输出：23

提示

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

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

2.分析

2.1 传统for循环

最简单的方法就是使用for循环，时间复杂度为$O(n^2)$，空间复杂度为$O(1)$。

具体解法：

• 第一层for循环i，代表子数组的起始位置
• 第二层for循环j，代表子数组的终止位置。
• 每次遍历，将nums i 到 j 的所有数累加到 current_sum 中。
• 每次遍历，将current_sum与max_sum进行比较，更新max_sum。
• 最后返回max_sum。

2.2 动态规划思路

状态定义：

• dp[i] 表示以 nums[i] 结尾的连续子数组的最大和

状态转移方程：

• 对于每个位置 i，我们有两个选择：
  1. 将当前元素 nums[i] 加到前面的子数组中：dp[i-1] + nums[i]
  2. 从当前元素 nums[i] 重新开始：nums[i]
• 因此：dp[i] = max(dp[i-1] + nums[i], nums[i])

边界条件：

• dp[0] = nums[0]

最终答案：

• 所有 dp[i] 中的最大值

优化思路

注意到我们只需要前一个状态 dp[i-1]，所以可以用一个变量来代替整个 dp 数组，将空间复杂度从 O(n) 优化到 O(1)。

3. Python 代码实现

方法一：标准动态规划（O(n) 空间）

def maxSubArray(nums):
    """
    动态规划解法 - 标准版本
    时间复杂度: O(n)
    空间复杂度: O(n)
    """
    n = len(nums)
    if n == 0:
        return 0
    
    # dp[i] 表示以 nums[i] 结尾的最大子数组和
    dp = [0] * n
    dp[0] = nums[0]
    max_sum = dp[0]
    
    for i in range(1, n):
        dp[i] = max(dp[i-1] + nums[i], nums[i])
        max_sum = max(max_sum, dp[i])
    
    return max_sum

方法二：空间优化版本（O(1) 空间）- 推荐

def maxSubArray(nums):
    """
    动态规划解法 - 空间优化版本
    时间复杂度: O(n)
    空间复杂度: O(1)
    """
    if not nums:
        return 0
    
    # current_sum: 以当前元素结尾的最大子数组和
    # max_sum: 全局最大子数组和
    current_sum = max_sum = nums[0]
    
    for i in range(1, len(nums)):
        # 要么继续前面的子数组，要么从当前元素重新开始
        current_sum = max(current_sum + nums[i], nums[i])
        # 更新全局最大值
        max_sum = max(max_sum, current_sum)
    
    return max_sum

算法执行过程示例

以 nums = [-2,1,-3,4,-1,2,1,-5,4] 为例：

i	nums[i]	current_sum	max_sum
0	-2	-2	-2
1	1	1	1
2	-3	-2	1
3	4	4	4
4	-1	3	4
5	2	5	5
6	1	6	6
7	-5	1	6
8	4	5	6

最终结果：6

测试代码

# 测试用例
def test_maxSubArray():
    assert maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) == 6
    assert maxSubArray([1]) == 1
    assert maxSubArray([5,4,-1,7,8]) == 23
    assert maxSubArray([-1]) == -1
    assert maxSubArray([-2,-1]) == -1
    print("所有测试用例通过！")

test_maxSubArray()

复杂度分析

• 时间复杂度：O(n)，只需要遍历数组一次
• 空间复杂度：O(1)，只使用了常数个额外变量

这个解法是解决最大子数组和问题的最优解，既简洁又高效。

4. 视频：

（1）最大子数组和题目理解（2）最大子数组和题目分析（3）最大子数组和思路梳理