30 连续子数组的最大和

题目描述

输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。

示例：

输入: [1, -2, 3, 10, -4, 7, 2, -5]
输出: 18 (子数组[3,10,-4,7,2])

解题思路

核心思想：动态规划。设dp[i]表示以第i个元素结尾的最大子数组和。

状态转移方程：

• dp[i] = max(dp[i-1] + nums[i], nums[i])
• 即：要么扩展前面的子数组，要么从当前元素重新开始

时间复杂度：O(n) 空间复杂度：O(n) 或 O(1)（优化后）

Python 实现

def find_greatest_sum_of_subarray(nums):
    """
    求连续子数组的最大和

    Args:
        nums: 整型数组

    Returns:
        int: 最大子数组和
    """
    if not nums:
        return 0

    max_sum = nums[0]
    current_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


# 动态规划版本（记录子数组）
def find_greatest_sum_of_subarray_with_dp(nums):
    """
    动态规划版本，返回最大和及其子数组
    """
    if not nums:
        return 0, []

    dp = [0] * len(nums)
    dp[0] = nums[0]
    max_sum = nums[0]
    end_idx = 0

    for i in range(1, len(nums)):
        dp[i] = max(dp[i-1] + nums[i], nums[i])
        if dp[i] > max_sum:
            max_sum = dp[i]
            end_idx = i

    # 找出子数组的起始位置
    start_idx = end_idx
    current_sum = max_sum
    while start_idx > 0 and current_sum != nums[start_idx]:
        current_sum -= nums[start_idx]
        start_idx -= 1

    return max_sum, nums[start_idx:end_idx+1]


# 测试代码
if __name__ == "__main__":
    test_cases = [
        [1, -2, 3, 10, -4, 7, 2, -5],
        [-2, -3, -1, -5],
        [1, 2, 3, 4, 5],
        [-1, 2, 3, -2, 4],
    ]

    for nums in test_cases:
        max_sum, subarray = find_greatest_sum_of_subarray_with_dp(nums)
        print(f"{nums} → 最大和: {max_sum}, 子数组: {subarray}")

# 输出:
# [1, -2, 3, 10, -4, 7, 2, -5] → 最大和: 18, 子数组: [3, 10, -4, 7, 2]
# [-2, -3, -1, -5] → 最大和: -1, 子数组: [-1]
# [1, 2, 3, 4, 5] → 最大和: 15, 子数组: [1, 2, 3, 4, 5]
# [-1, 2, 3, -2, 4] → 最大和: 7, 子数组: [2, 3, -2, 4]

图解

示例: [1, -2, 3, 10, -4, 7, 2, -5]

动态规划过程:
i=0: dp[0] = 1, max=1
i=1: dp[1] = max(1-2, -2) = -1, max=1
i=2: dp[2] = max(-1+3, 3) = 3, max=3
i=3: dp[3] = max(3+10, 10) = 13, max=13
i=4: dp[4] = max(13-4, -4) = 9, max=13
i=5: dp[5] = max(9+7, 7) = 16, max=16
i=6: dp[6] = max(16+2, 2) = 18, max=18
i=7: dp[7] = max(18-5, -5) = 13, max=18

最大和: 18

找出子数组: 从dp[6]=18往前推
18-2=16, 继续往前
16-7=9, 继续往前
9-(-4)=13, 继续往前
13-10=3, 继续往前
3≠3, 停止

子数组: [3, 10, -4, 7, 2]