Python求解最大子序和：从暴力法到动态规划的优化之路

Leo

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

原创

本文详细解析Python中求解最大子序和的三种算法。从基础的暴力枚举法入手，分析其O(N^2)的时间瓶颈；接着介绍分治策略，将问题划分为左右子序列及跨越中点的情况，实现O(NlogN)复杂度；最终重点讲解动态规划方法，通过维护当前最大和与全局最大和，将时间复杂度优化至O(N)，运行时间从14.7秒缩短至0.1秒，是解决该问题的最优方案。

问题描述与示例

描述

给定一个整数序列（至少包含 1 个元素），需要从中找出一个连续的非空子序列，使得该子序列的元素之和最大。例如，对于输入序列 [-2,1,-3,4,-1,2,1,-5,4]，连续子序列 [4,-1,2,1] 的和最大，结果为 6。

暴力枚举法实现与性能分析

我 v1.0


class Solution:
  def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    l = len(nums)
    i = 0
    result = nums[0]
    while i < l:
      sums = []
      temp = 0
      for j in range(i, l):
        temp+=nums[j]
        sums.append(temp)
      if result < max(sums):
        result = max(sums)
      i+=1
    return result

测试结果如下：

本地运行时间为14.7s，说明我的方法太粗暴了。应该寻找更好的算法。

我优化后v1.1。优化方案，去掉sums数组，节省空间。但时间复杂度仍然不变。


  l = len(nums)
    i = 0
    result = nums[0]
    while i < l:
      temp = 0
      for j in range(i, l):
        temp+=nums[j]
        if result < temp:
          result = temp
      i+=1
    return result

仍然只通过200/202测试用例，仍然超出时间限制。但本地运行时间为8.3s。有进步。

分治法思路解析

别人，分治法。时间复杂度O(NlogN)

将输入的序列分成两部分，这个时候有三种情况。 1）最大子序列在左半部分 2）最大子序列在右半部分 3）最大子序列跨越左右部分。

前两种情况通过递归求解，第三种情况可以通过。

分治法代码大概如下，emmm。。。目前还没有完全理解。


def maxC2(ls,low,upp): 
  #"divide and conquer" 
  if ls is None: return 0 
  elif low==upp: return ls[low] 

  mid=(low+upp)/2 #notice: in the higher version python, “/” would get the real value 
  lmax,rmax,tmp,i=0,0,0,mid 
  while i>=low: 
    tmp+=ls[i] 
    if tmp>lmax: 
      lmax=tmp 
    i-=1 
  tmp=0 
  for k in range(mid+1,upp): 
    tmp+=ls[k] 
    if tmp>rmax: 
      rmax=tmp 
  return max3(rmax+lmax,maxC2(ls,low,mid),maxC2(ls,mid+1,upp)) 

def max3(x,y,z): 
  if x>=y and x>=z: 
    return x 
  return max3(y,z,x)

动态规划最优解法

动态规划算法，时间复杂度为O(n)。分析：寻找最优子结构。


   l = len(nums)
    i = 0
    sum = 0
    MaxSum = nums[0]
    while i < l:
      sum+=nums[i]
      if sum > MaxSum:
          MaxSum = sum
      if sum < 0:
        sum = 0
      i+=1
    return MaxSum

Oh！My god！！！！！！！！！！！运行只花了0.2s！！！！！！！！！！！！！！！这也太强了吧！！

优化后,运行时间0.1s.


 sum = 0
    MaxSum = nums[0]
    for i in range(len(nums)):
      sum += nums[i]
      if sum > MaxSum:
        MaxSum = sum
      if sum < 0:
        sum = 0
    return MaxSum

其中

sum += nums[i]必须紧挨。