python實(shí)現(xiàn)最大子序和（分治+動(dòng)態(tài)規(guī)劃）

給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

進(jìn)階:

如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

思路：

首先我們分析題目，我們思考，為什么最大和的連續(xù)子數(shù)組不包含其他的元素而是這幾個(gè)呢？因?yàn)槿绻覀兿朐诂F(xiàn)有的基礎(chǔ)上去擴(kuò)展當(dāng)前連續(xù)子數(shù)組，相鄰的元素是一定要被加入的，而相鄰元素中可能會(huì)減損當(dāng)前的和。

思路一：

遍歷法，On:

算法過程：遍歷數(shù)組，用onesum去維護(hù)當(dāng)前元素加起來的和。當(dāng)onesum出現(xiàn)小于0的情況時(shí)，我們把它設(shè)為0。然后每次都更新全局最大值。

class Solution:
  def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    #onesum維護(hù)當(dāng)前的和
    onesum = 0
    maxsum = nums[0]
    for i in range(len(nums)):
      onesum += nums[i]
      maxsum = max(maxsum, onesum)
      #出現(xiàn)onesum<0的情況，就設(shè)為0，重新累積和
      if onesum < 0:
        onesum = 0
    return maxsum

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

當(dāng)我們的i選出來后，加入onesum。這時(shí)有2種情況

1）假設(shè)我們這個(gè)onesum一直大于0，從未被<0過。那也就是說我們計(jì)算的每一次的onesum都大于0，而每一次計(jì)算的onesum都是包括開頭元素的一段子序列（尾部一直隨i變化）?？此莆覀儧]有考慮所有可能序列，但實(shí)際上所有可能的序列都已經(jīng)被考慮過了。這里簡單講一下，待會(huì)po原文。

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

   b)以當(dāng)前子序列結(jié)尾為結(jié)尾，中間任一處開頭的序列。這種情況一定的和小于以當(dāng)前子序列開頭為開頭，結(jié)尾為結(jié)尾的序列。因?yàn)榍懊嫒笔У哪且欢谓?jīng)過我們的前提，它也是加和大于0的。

   c)以中間元素為開頭和結(jié)尾的序列。和小于以當(dāng)前子序列開頭為開頭，此分序列結(jié)尾為結(jié)尾的序列。因?yàn)榍懊嫒笔У哪且欢谓?jīng)過我們的前提，它也是加和大于0的。

2）出現(xiàn)小于0的情況，就說明我們當(dāng)前形成的這個(gè)子序是第一次出現(xiàn)小于0的情況?，F(xiàn)在至少我們要新形成的連續(xù)數(shù)組不能在整個(gè)的包括之前的連續(xù)子序了，因?yàn)槲覀冊谥暗哪莻€(gè)連續(xù)子序里加出了<0的情況。但問題是我們需不需要保留一些呢？是不是所有以當(dāng)前子序結(jié)尾為結(jié)尾的任意開頭的子序都要被舍棄呢？答案是是的，因?yàn)槟且欢我惨欢ㄐ∮?，因?yàn)槟且欢蔚募雍蜁?huì)小于以當(dāng)前子序開頭為開頭，當(dāng)前子序結(jié)尾為結(jié)尾的序列（見前面證明）。于是拋棄掉它們，重新開始新的子序。

思路二：

動(dòng)態(tài)規(guī)劃 On

算法過程：

設(shè)sum[i]為以第i個(gè)元素結(jié)尾的最大的連續(xù)子數(shù)組的和。假設(shè)對于元素i，所有以它前面的元素結(jié)尾的子數(shù)組的長度都已經(jīng)求得，那么以第i個(gè)元素結(jié)尾且和最大的連續(xù)子數(shù)組實(shí)際上，要么是以第i-1個(gè)元素結(jié)尾且和最大的連續(xù)子數(shù)組加上這個(gè)元素，要么是只包含第i個(gè)元素，即sum[i]= max(sum[i-1] + a[i], a[i])?？梢酝ㄟ^判斷sum[i-1] + a[i]是否大于a[i]來做選擇，而這實(shí)際上等價(jià)于判斷sum[i-1]是否大于0。由于每次運(yùn)算只需要前一次的結(jié)果，因此并不需要像普通的動(dòng)態(tài)規(guī)劃那樣保留之前所有的計(jì)算結(jié)果，只需要保留上一次的即可，因此算法的時(shí)間和空間復(fù)雜度都很小

class Solution:
 
 
  def maxSubArray(self, nums): 
    """ 
    :type nums: List[int] 
    :rtype: int 
    """ 
    length=len(nums) 
    for i in range(1,length): 
      #當(dāng)前值的大小與前面的值之和比較，若當(dāng)前值更大，則取當(dāng)前值，舍棄前面的值之和 
      subMaxSum=max(nums[i]+nums[i-1],nums[i]) 
      nums[i]=subMaxSum#將當(dāng)前和最大的賦給nums[i]，新的nums存儲(chǔ)的為和值 
    return max(nums) 

算法證明：這道題的代碼我直接使用了題目數(shù)據(jù)中的nums數(shù)組，因?yàn)橹灰闅v一遍。nums[i]表示的是以當(dāng)前這第i號元素結(jié)尾（看清了一定要包含當(dāng)前的這個(gè)i）的話，最大的值無非就是看以i-1結(jié)尾的最大和的子序能不能加上我這個(gè)nums[i]，如果nums[i]>0的話，則加上。注意我代碼中沒有顯式地去這樣判斷，不過我的Max表達(dá)的就是這個(gè)意思，然后我們把nums[i]確定下來。

思路三：

分治遞歸

算法過程：

分治法，最大子序和要么在左半部分，要么在右半部分，要么就橫跨兩部分（即包括左半部分的最后一個(gè)元素，和右半部分的第一個(gè)元素）。返回這三種情況的最大值即可。第三種情況，其中包括左半部分最后一個(gè)元素的情形，需要挨個(gè)往前遍歷，更新最大值。包含右半部分的第一個(gè)元素的情況類似?？偟臅r(shí)間復(fù)雜度O(nlogn)

class Solution(object):
  def maxSubArray(self, nums):
    #主函數(shù)
    left = 0
    #左右邊界
    right = len(nums)-1
    #求最大和
    maxSum = self.divide(nums,left,right)
    return maxSum
    
  def divide(self,nums,left,right):
    #如果只有一個(gè)元素就返回
    if left==right:
      return nums[left]
    #確立中心點(diǎn)
    center = (left+right)//2
    #求子序在中心點(diǎn)左邊的和
    leftMaxSum = self.divide(nums,left,center)
    #求子序在中心點(diǎn)右邊的和
    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:
        #不斷更新左區(qū)塊的最大值
        leftBorderSum = leftSum
      
    rightBorderSum = nums[center+1]
    rightSum = nums[center+1]
    for i in range(center+2,right+1):
      rightSum += nums[i]
      if rightSum>rightBorderSum:
        #不斷更新右區(qū)塊的最大值
        rightBorderSum = rightSum
    #左邊界的和 + 右邊那塊的和
    BorderSum = leftBorderSum + rightBorderSum
    return max(leftMaxSum,rightMaxSum,BorderSum)

算法證明：

總的來說還是超級巧妙的。不斷的切不斷的切數(shù)組，把一塊數(shù)組看成左中右三個(gè)部分。實(shí)際上這有點(diǎn)像枚舉，但我們在枚舉時(shí)利用了二分的思路，優(yōu)化了很多。所以枚舉當(dāng)然可以達(dá)到我們的目標(biāo)了，因?yàn)槲覀儾粩嘣谟?jì)算以一定包括中間節(jié)點(diǎn)的子序的最大和。

總結(jié)：

今天寫了很多很多，都沒時(shí)間復(fù)習(xí)了。。。但是收獲還是很大的。比如動(dòng)態(tài)規(guī)劃，不一定一定要建立數(shù)組然后返回?cái)?shù)組的最后一項(xiàng)，動(dòng)態(tài)規(guī)劃其實(shí)是很靈活的。但是動(dòng)態(tài)規(guī)劃的每一項(xiàng)代表的意義要想好。

分治遞歸，實(shí)際在幫我們算所有數(shù)組只不過用了二分的思路優(yōu)化。

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。