Python实现数组连续最大子数组和：从暴力法到动态规划优化

半杯拿铁

发布时间：2026-10-13| 6人浏览过

原创

本文详细介绍Python中求解连续子数组最大和的四种方法：蛮力法、重复利用子数组和、动态规划及优化动态规划。通过对比O(n^3)、O(n^2)、O(n)时间复杂度和空间占用，展示如何从基础逻辑逐步优化至最优解，并附带完整代码与性能分析。

问题描述与示例

题目要求：

给定一个包含 n 个元素的数组，元素值可为正数或负数。我们需要找出该数组中所有可能的连续子数组（由连续个元素组成），并计算每个子数组的元素之和，最终确定这些和中最大的数值。例如，对于数组 [1, -2, 4, 8, -4, 7, -1, -5]，其最大和的子数组为 [4, 8, -4, 7]，计算得出的最大和为 15。

解决方案：

蛮力法
重复利用已计算的子数组和
动态规划
优化的动态规划

方法一：蛮力法

1. 蛮力法

核心思路是枚举所有可能的子数组，计算它们的和，然后从所有和中选出最大值。

代码实现：


#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/1/29 21:59
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
def maxSubArrSum(arr):
  if arr == None or len(arr) <= 0:
    print('参数不合理！')
    return
  thisSum = 0
  maxSum = 0
  i = 0
  while i < len(arr):
    j = i
    while j < len(arr):# j 控制连续子数组包含的元素个数
      thisSum = 0
      k = i # k 表示连续子数组开始的下标
      while k < j:
        thisSum += arr[k]
        k += 1
      if thisSum > maxSum:
        maxSum = thisSum
      j += 1
    i += 1
  return maxSum


if __name__ == '__main__':
  arr = [1, -2, 4, 8, -4, 7, -1, -5]
  print('1 max sub array sum:', maxSubArrSum(arr))

运行结果：

算法性能分析：该方法的实现涉及三层嵌套循环，因此时间复杂度为 O(n^3)；

方法二：重复利用子数组和

2. 重复利用已计算的子数组和

利用数学关系 sum[i, j] = sum[i, j-1] + arr[j]，在计算当前子数组和时，可以直接基于前一步计算出的 sum[i, j-1] 进行累加，无需从头重新计算。这种策略减少了重复运算，提升了执行效率。

代码实现：


#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/1/30 10:53
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
def maxSubArrSum(arr):
  if arr == None or len(arr) <= 0:
    print('参数不合理！')
    return
  maxSum = -2 ** 31
  i = 0
  while i < len(arr): # i: 0~7
    sums = 0
    j = i
    while j < len(arr): # j: 0~7
      sums += arr[j] # sums 重复利用
      if sums > maxSum: # 每加一次就判断一次
        maxSum = sums
      j += 1
    i += 1
  return maxSum


if __name__ == '__main__':
  arr = [1, -2, 4, 8, -4, 7, -1, -5]
  print('2 max sub array sum:', maxSubArrSum(arr))

运行结果：

算法性能分析：该方法使用双重循环遍历，时间复杂度优化至 O(n^2)；

方法三：动态规划

3. 动态规划

首先根据数组最后一个元素 arr[n-1] 与最大子数组的关系，将问题分解为以下三种情况讨论： (包含或不包含，若包含则必以最后一个元素结尾；若不包含，则要么最后一个元素单独构成最大子数组，要么最大子数组完全位于 arr[1…n-2] 中) (1) 最大子数组包含 arr[n-1]，即最大子数组以 arr[n-1] 结尾； (2) arr[n-1] 单独构成最大子数组； (3) 最大子数组不包含 arr[n-1]，此时问题转化为求 arr[1…n-2] 的最大子数组。由此可得状态转移方程：

代码实现：


#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/1/30 11:19
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
def maxSubArrSum(arr):
  if arr == None or len(arr) <= 0:
    print('参数不合理！')
    return
  n = len(arr)
  End = [None] * n # End[i] 表示包含 arr[i] 的最大子数组和
  All = [None] * n # All[i] 表示最大子数组和
  End[n - 1] = arr[n - 1]
  All[n - 1] = arr[n - 1]
  End[0] = All[0] = arr[0]
  i = 1
  while i < n:
    End[i] = max(End[i - 1] + arr[i], arr[i]) # i=1时若arr[0]<0,则从arr[1]重新开始
    All[i] = max(End[i], All[i - 1])
    i += 1
  return All[n - 1]


if __name__ == '__main__':
  arr = [1, -2, 4, 8, -4, 7, -1, -5]
  print('3 max sub array sum:', maxSubArrSum(arr))

运行结果：

算法性能分析：时间复杂度为 O(n)；由于额外申请了两个长度为 n 的数组来存储中间状态，所以空间复杂度为 O(n)；

方法四：优化的动态规划

4. 优化的动态规划

在方法3中，每次迭代实际上只依赖于 End[i-1] 与 All[i-1] 的值，而非整个数组的历史数据。因此，可以定义两个变量来分别保存 End[i-1] 与 All[i-1] 的值，并通过反复更新这两个变量来实现状态转移，从而节省空间。

代码实现：


#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/1/30 11:55
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
def maxSubArrSum(arr):
  if arr == None or len(arr) <= 0:
    print('参数不合理！')
    return
  nAll = arr[0] # 最大子数组和
  nEnd = arr[0] # 包含最后一个元素的最大子数组和
  i = 1
  while i < len(arr):
    nEnd = max(nEnd + arr[i], arr[i])
    nAll = max(nEnd, nAll)
    i += 1
  return nAll


if __name__ == '__main__':
  arr = [1, -2, 4, 8, -4, 7, -1, -5]
  print('4 max sub array sum:', maxSubArrSum(arr))

运行结果：

算法性能分析：时间复杂度为 O(n)；空间复杂度优化至 O(1)；

引申：确定最大子数组范围

引申问题：

在已知子数组的最大和之后，如何进一步确定该最大子数组的具体范围（即起始和结束位置）？

解决思路：

代码实现：


#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/1/30 12:01
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
class Test:
  def __init__(self):
    self.begin = 0 # 记录最大子数组起始位置
    self.end = 0 # 记录最大子数组结束位置

  def maxSubArrSum(self, arr):
    n = len(arr)
    maxSum = -2 ** 31 # 子数组最大值
    nSum = 0 # 包含子数组最后一位的最大值
    nStart = 0
    i = 0
    while i < n:
      if nSum < 0:
        nSum = arr[i]
        nStart = i
      else:
        nSum += arr[i]
      if nSum > maxSum:
        maxSum = nSum
        self.begin = nStart
        self.end = i
      i += 1
    return maxSum

  def getBegin(self):
    return self.begin

  def getEnd(self):
    return self.end


if __name__ == '__main__':
  arr = [1, -2, 4, 8, -4, 7, -1, -5]
  t = Test()
  print('连续最大和为:', t.maxSubArrSum(arr))
  print('begin at ', t.getBegin())
  print('end at ', t.getEnd())

运行结果：