Python实现最大子序和：分治与动态规划详解

最大子序和问题定义

给定一个整数数组 nums，需要找到一个具有最大和的连续子数组（该子数组至少包含一个元素），并返回其最大和。

示例展示如下：

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

进阶挑战：

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

思路分析：

首先分析题目，思考为什么最大和的连续子数组只包含特定元素。原因在于，若要在现有基础上扩展当前连续子数组，必须加入相邻元素，而相邻元素可能会减损当前的和。

遍历法实现与证明

思路一：

遍历法，时间复杂度 O(n)：

算法过程：遍历数组，使用 onesum 维护当前元素累加的和。当 onesum 出现小于 0 的情况时，将其重置为 0。每次迭代后更新全局最大值。

class Solution:
  def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    #onesum维护当前的和
    onesum = 0
    maxsum = nums[0]
    for i in range(len(nums)):
      onesum += nums[i]
      maxsum = max(maxsum, onesum)
      #出现onesum<0的情况，就设为0，重新累积和
      if onesum < 0:
        onesum = 0
    return maxsum

算法证明：初始时假设数组为空，将每次选择 nums[i] 加入 onesum 视为当前数组新增一个元素，即以动态的眼光思考。过程简单且代码简短，但其有效性源于加和是按顺序从数组第一个元素开始计算的。

当确定 i 并加入 onesum 后，存在两种情况：

1）假设 onesum 一直大于 0，从未小于等于 0。这意味着每次计算的 onesum 都大于 0，且每次计算的 onesum 都是包括开头元素的一段子序列（尾部随 i 变化）。看似未考虑所有可能序列，但实际上所有可能的序列都已被覆盖。简要说明如下，详见原文：

a) 以当前子序列开头为起点，中间任一处结尾的序列。这种情况一直在扫描并更新保存，因此不会丢失信息。

b) 以当前子序列结尾为终点，中间任一处开头的序列。这种情况的和一定小于以当前子序列开头为起点、结尾为终点的序列。因为前面缺失的那一段经过前提判断，其加和大于 0。

c) 以中间元素为起点和终点的序列。其和小于以当前子序列开头为起点、此分序列结尾为终点的序列。因为前面缺失的那一段经过前提判断，其加和大于 0。

2）出现小于 0 的情况，说明当前形成的子序列首次出现总和小于 0。此时，新的连续数组不能包含之前的整个连续子序列，因为在之前的子序列中累加出了小于 0 的结果。问题是是否需要保留部分？是否所有以当前子序列结尾为终点的任意开头的子序列都要被舍弃？答案是肯定的，因为那一段的和也一定小于 0（见前述证明）。因此，抛弃它们，重新开始新的子序列。

动态规划优化策略

思路二：

动态规划，时间复杂度 O(n)

算法过程：

设 sum[i] 为以第 i 个元素结尾的最大连续子数组的和。假设对于元素 i，所有以其前面元素结尾的子数组长度已求得，那么以第 i 个元素结尾且和最大的连续子数组，要么是以第 i-1 个元素结尾且和最大的连续子数组加上当前元素，要么只包含第 i 个元素。即 sum[i] = max(sum[i-1] + a[i], a[i])。通过判断 sum[i-1] + a[i] 是否大于 a[i] 来做选择，这等价于判断 sum[i-1] 是否大于 0。由于每次运算只需前一次结果，无需像普通动态规划那样保留所有计算结果，只需保留上一次结果，因此算法的时间和空间复杂度都很小。

class Solution:
 
 
  def maxSubArray(self, nums): 
    """ 
    :type nums: List[int] 
    :rtype: int 
    """ 
    length=len(nums) 
    for i in range(1,length): 
      #当前值的大小与前面的值之和比较，若当前值更大，则取当前值，舍弃前面的值之和 
      subMaxSum=max(nums[i]+nums[i-1],nums[i]) 
      nums[i]=subMaxSum#将当前和最大的赋给nums[i]，新的nums存储的为和值 
    return max(nums) 

算法证明：代码直接使用了题目数据中的 nums 数组，因为只需遍历一遍。nums[i] 表示以当前第 i 号元素结尾（必须包含当前 i）的最大值，无非是看以 i-1 结尾的最大和子序能否加上 nums[i]。如果 nums[i] > 0，则加上。代码中虽未显式判断，但 Max 表达此意，确定 nums[i] 后继续。

分治递归算法解析

思路三：

分治递归

算法过程：

分治法中，最大子序和要么在左半部分，要么在右半部分，要么横跨两部分（即包括左半部分的最后一个元素和右半部分的第一个元素）。返回这三种情况的最大值。第三种情况中，包含左半部分最后一个元素的情形需挨个往前遍历更新最大值；包含右半部分第一个元素的情形类似。总的时间复杂度为 O(nlogn)。

class Solution(object):
  def maxSubArray(self, nums):
    #主函数
    left = 0
    #左右边界
    right = len(nums)-1
    #求最大和
    maxSum = self.divide(nums,left,right)
    return maxSum
    
  def divide(self,nums,left,right):
    #如果只有一个元素就返回
    if left==right:
      return nums[left]
    #确立中心点
    center = (left+right)//2
    #求子序在中心点左边的和
    leftMaxSum = self.divide(nums,left,center)
    #求子序在中心点右边的和
    rightMaxSum = self.divide(nums,center+1,right)
    
    #求子序横跨2边的和，分成左边界和和右边界和
    leftBorderSum = nums[center]
    leftSum = nums[center]
    for i in range(center-1,left-1,-1):
      leftSum += nums[i]
      if leftSum>leftBorderSum:
        #不断更新左区块的最大值
        leftBorderSum = leftSum
      
    rightBorderSum = nums[center+1]
    rightSum = nums[center+1]
    for i in range(center+2,right+1):
      rightSum += nums[i]
      if rightSum>rightBorderSum:
        #不断更新右区块的最大值
        rightBorderSum = rightSum
    #左边界的和 + 右边那块的和
    BorderSum = leftBorderSum + rightBorderSum
    return max(leftMaxSum,rightMaxSum,BorderSum)

算法证明：

整体思路巧妙，不断切割数组，将一块数组视为左、中、右三个部分。这类似于枚举，但利用二分思路优化了大量计算。因此枚举能达到目标，因为不断计算以一定包括中间节点的子序的最大和。

算法总结与启示

总结：

本文内容较多，虽无时间复习，但收获颇丰。例如动态规划不一定非要建立数组并返回最后一项，动态规划其实很灵活，但需明确每一项代表的意义。

分治递归实际在帮我们计算所有数组，只不过用了二分思路进行优化。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。