python实现最大子序和（分治+动态规划）-创新互联

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

示例:

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

进阶:

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

思路：

首先我们分析题目，我们思考，为什么大和的连续子数组不包含其他的元素而是这几个呢？因为如果我们想在现有的基础上去扩展当前连续子数组，相邻的元素是一定要被加入的，而相邻元素中可能会减损当前的和。

思路一：

遍历法，On:

算法过程：遍历数组，用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