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

示例:

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

進階:

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

思路：

首先我們分析題目，我們思考，為什么最大和的連續(xù)子數(shù)組不包含其他的元素而是這幾個呢？因為如果我們想在現(xiàn)有的基礎(chǔ)上去擴展當(dāng)前連續(xù)子數(shù)組，相鄰的元素是一定要被加入的，而相鄰元素中可能會減損當(dāng)前的和。

思路一：

遍歷法，On:

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

class Solution:
  def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    #onesum維護當(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ù)組是個空的，把我們每次選一個nums[i]加入onesum看成當(dāng)前數(shù)組新增了一個元素，也就是用動態(tài)的眼光去思考。過程很簡單，代碼很短，但為什么這樣就能達到效果呢？我們進行的加和是按順序來的，從數(shù)組第一個開始加。

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

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

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

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

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

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

思路二：

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

算法過程：

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

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

思路三：

分治遞歸

算法過程：

分治法，最大子序和要么在左半部分，要么在右半部分，要么就橫跨兩部分（即包括左半部分的最后一個元素，和右半部分的第一個元素）。返回這三種情況的最大值即可。第三種情況，其中包括左半部分最后一個元素的情形，需要挨個往前遍歷，更新最大值。包含右半部分的第一個元素的情況類似?？偟臅r間復(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):
    #如果只有一個元素就返回
    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:
        #不斷更新左區(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ù)組看成左中右三個部分。實際上這有點像枚舉，但我們在枚舉時利用了二分的思路，優(yōu)化了很多。所以枚舉當(dāng)然可以達到我們的目標了，因為我們不斷在計算以一定包括中間節(jié)點的子序的最大和。

總結(jié)：

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

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

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

最新評論