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

算法證明：一開始思考數組是個空的，把我們每次選一個nums[i]加入onesum看成當前數組新增了一個元素，也就是用動態的眼光去思考。過程很簡單，代碼很短，但為什么這樣就能達到效果呢？我們進行的加和是按順序來的，從數組第一個開始加。

當我們的i選出來后，加入onesum。這時有2種情況

1）假設我們這個onesum一直大于0，從未被<0過。那也就是說我們計算的每一次的onesum都大于0，而每一次計算的onesum都是包括開頭元素的一段子序列（尾部一直隨i變化）。看似我們沒有考慮所有可能序列，但實際上所有可能的序列都已經被考慮過了。這里簡單講一下，待會po原文。

   a)以當前子序列開頭為開頭，中間任一處結尾的序列。這種情況是一直在掃描的，也有一直保存更新，所以不用怕丟失信息。

   b)以當前子序列結尾為結尾，中間任一處開頭的序列。這種情況一定的和小于以當前子序列開頭為開頭，結尾為結尾的序列。因為前面缺失的那一段經過我們的前提，它也是加和大于0的。

   c)以中間元素為開頭和結尾的序列。和小于以當前子序列開頭為開頭，此分序列結尾為結尾的序列。因為前面缺失的那一段經過我們的前提，它也是加和大于0的。

2）出現小于0的情況，就說明我們當前形成的這個子序是第一次出現小于0的情況。現在至少我們要新形成的連續數組不能在整個的包括之前的連續子序了，因為我們在之前的那個連續子序里加出了<0的情況。但問題是我們需不需要保留一些呢？是不是所有以當前子序結尾為結尾的任意開頭的子序都要被舍棄呢？答案是是的，因為那一段也一定小于0，因為那一段的加和會小于以當前子序開頭為開頭，當前子序結尾為結尾的序列（見前面證明）。于是拋棄掉它們，重新開始新的子序。

思路二：

動態規劃 On

算法過程：

設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)

算法證明：

總的來說還是超級巧妙的。不斷的切不斷的切數組，把一塊數組看成左中右三個部分。實際上這有點像枚舉，但我們在枚舉時利用了二分的思路，優化了很多。所以枚舉當然可以達到我們的目標了，因為我們不斷在計算以一定包括中間節點的子序的最大和。

總結：

今天寫了很多很多，都沒時間復習了。。。但是收獲還是很大的。比如動態規劃，不一定一定要建立數組然后返回數組的最后一項，動態規劃其實是很靈活的。但是動態規劃的每一項代表的意義要想好。

分治遞歸，實際在幫我們算所有數組只不過用了二分的思路優化。

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。