摘要：動態(tài)規(guī)劃法用表示最大子數(shù)組的結(jié)束下標為的情形，則對于，有這樣就有了一個子結(jié)構(gòu)，對于初始情形，遍歷就能得到這個數(shù)組，其最大者即可最大子數(shù)組的和。動態(tài)規(guī)劃法想法巧妙，運行效率也高，但是沒有普遍的適用性。

??本文將介紹計算機算法中的經(jīng)典問題——最大子數(shù)組問題（maximum subarray problem）。所謂的最大子數(shù)組問題，指的是：給定一個數(shù)組A，尋找A的和最大的非空連續(xù)子數(shù)組。比如，數(shù)組 A = [-2, -3, 4, -1, -2, 1, 5, -3]， 最大子數(shù)組應為[4, -1, -2, 1, 5],其和為7。
??首先，如果A中的元素全部為正（或非負數(shù)），則最大子數(shù)組就是它本身；如果A中的元素全部為負，則最大子數(shù)組就是第一個元素組成的數(shù)組。以上兩種情形是平凡的，那么，如果A中的元素既有正數(shù)，又有負數(shù)，則該如何求解呢？本文將介紹該問題的四種算法，并給出后面三種算法的Python語言實現(xiàn)，解決該問題的算法如下：

暴力求解

分治法

Kadane算法

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

??下面就這四種算法做詳細介紹。

??假設(shè)數(shù)組的長度為n，暴力求解方法的思路是很簡單的，就是將子數(shù)組的開始坐標和結(jié)束坐標都遍歷一下，這樣共有$C_{n}^{2}$中組合方式，再考慮這所有組合方式中和最大的情形即可。
??該算法的運行時間為$O(n^{2})$,效率是很低的。那么，還有其它高效的算法嗎？

??分治法的基本思想是將問題劃分為一些子問題，子問題的形式與原問題一樣，只是規(guī)模更小，遞歸地求解出子問題，如果子問題的規(guī)模足夠小，則停止遞歸，直接求解，最后將子問題的解組合成原問題的解。
??對于最大子數(shù)組，我們要尋求子數(shù)組A[low...high]的最大子數(shù)組。令mid為該子數(shù)組的中央位置，我們考慮求解兩個子數(shù)組A[low...mid]和A[mid+1...high]。A[low...high]的任何連續(xù)子數(shù)組A[i...j]所處的位置必然是以下三種情況之一：

完全位于子數(shù)組A[low...mid]中,因此$lowleq ileq j leq mid.$

完全位于子數(shù)組A[mid+1...high]中,因此$mid< ileq j leq high.$

跨越了中點，因此$low leq i leq mid < j leq high.$

因此，最大子數(shù)組必定為上述3種情況中的最大者。對于情形1和情形2，可以遞歸地求解，剩下的就是尋找跨越中點的最大子數(shù)組。
??任何跨越中點的子數(shù)組都是由兩個子數(shù)組A[i...mid]和A[mid+1...j]組成，其中$low leq i leq mid$且$mid

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high):
left-sum = -inf
sum = 0
for i = mid downto low
    sum = sum + A[i]
    if sum > left-sum
        left-sum = sum
        max-left = i
        
right-sum = -inf
sum = 0
for j = mid+1 to high
    sum = sum + A[j]
    if sum > right-sum
        right-sum = sum
        max-right = i
        
return (max-left, max-right, left-sum+right+sum)

??有了FIND-MAX-CROSSING-SUBARRAY我們可以找到跨越中點的最大子數(shù)組，于是，我們也可以設(shè)計求解最大子數(shù)組問題的分治算法了，其偽代碼如下：

FIND-MAXMIMUM-SUBARRAY(A, low, high):
if high = low
    return (low, high, A[low])
else 
    mid = floor((low+high)/2)
    (left-low, left-high, left-sum) = FIND-MAXMIMUM-SUBARRAY(A, low, mid)
    (right-low, right-high, right-sum) = FIND-MAXMIMUM-SUBARRAY(A, mid+1, high)
    (cross-low, cross-high, cross-sum) = FIND-MAXMIMUM-SUBARRAY(A, low, mid, high)
    
    if left-sum >= right-sum >= cross-sum
        return (left-low, left-high, left-sum)
    else right-sum >= left-sum >= cross-sum
        return (right-low, right-high, right-sum)
    else
        return (cross-low, cross-high, cross-sum)

??顯然這樣的分治算法對于初學者來說，有點難度，但是熟能生巧, 多學多練也就不難了。該分治算法的運行時間為$O(n*logn).$

??Kadane算法的偽代碼如下：

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

??Kadane算法的簡單想法就是尋找所有連續(xù)的正的子數(shù)組（max_ending_here就是用來干這事的），同時，記錄所有這些連續(xù)的正的子數(shù)組中的和最大的連續(xù)數(shù)組。每一次我們得到一個正數(shù)，就將它與max_so_far比較，如果它的值比max_so_far大，則更新max_so_far的值。

?? 用MS[i]表示最大子數(shù)組的結(jié)束下標為i的情形，則對于i-1，有：
$$MS[i] = max{MS[i-1], A[i]}.$$
這樣就有了一個子結(jié)構(gòu)，對于初始情形，$MS[1]=A[1].$遍歷i, 就能得到MS這個數(shù)組，其最大者即可最大子數(shù)組的和。

?? 可以看到以上四種算法，每種都有各自的優(yōu)缺點。對于暴力求解方法，想法最簡單，但是算法效率不高。Kanade算法簡單高效，但是不易想到。分治算法運行效率高，但其分支過程的設(shè)計較為麻煩。動態(tài)規(guī)劃法想法巧妙，運行效率也高，但是沒有普遍的適用性。

?? 下面將給出分治算法，Kanade算法和動態(tài)規(guī)劃法來求解最大子數(shù)組問題的Python程序， 代碼如下：

# -*- coding: utf-8 -*-
__author__ = "Jclian"

import math

# find max crossing subarray in linear time
def find_max_crossing_subarray(A, low, mid, high):
    max_left, max_right = -1, -1

    # left part of the subarray
    left_sum = float("-Inf")
    sum = 0
    for i in range(mid, low - 1, -1):
        sum += A[i]
        if (sum > left_sum):
            left_sum = sum
            max_left = i

    # right part of the subarray
    right_sum = float("-Inf")
    sum = 0
    for j in range(mid + 1, high + 1):
        sum += A[j]
        if (sum > right_sum):
            right_sum = sum
            max_right = j

    return max_left, max_right, left_sum + right_sum

# using divide and conquer to solve maximum subarray problem
# time complexity: n*logn
def find_maximum_subarray(A, low, high):
    if (high == low):
        return low, high, A[low]
    else:
        mid = math.floor((low + high) / 2)
        left_low, left_high, left_sum = find_maximum_subarray(A, low, mid)
        right_low, right_high, right_sum = find_maximum_subarray(A, mid + 1, high)
        cross_low, cross_high, cross_sum = find_max_crossing_subarray(A, low, mid, high)
        if (left_sum >= right_sum and left_sum >= cross_sum):
            return left_low, left_high, left_sum
        elif (right_sum >= left_sum and right_sum >= cross_sum):
            return right_low, right_high, right_sum
        else:
            return cross_low, cross_high, cross_sum

# Python program to find maximum contiguous subarray
# Kadane’s Algorithm
def maxSubArraySum(a, size):
    max_so_far = float("-inf")
    max_ending_here = 0

    for i in range(size):
        max_ending_here = max_ending_here + a[i]
        if (max_so_far < max_ending_here):
            max_so_far = max_ending_here

        if max_ending_here < 0:
            max_ending_here = 0

    return max_so_far

# using dynamic programming to slove maximum subarray problem
def DP_maximum_subarray(arr):
    t = len(arr)
    MS = [0]*t
    MS[0] = arr[0]

    for i in range(1, t):
        MS[i] = max(MS[i-1]+arr[i], arr[i])

    return MS

def main():
    # example of array A
    A = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]
    # A = [-2, 2, -3, 4, -1, 2, 1, -5, 3]
    # A = [0,-2, 3, 5, -1, 2]
    # A = [-9, -2, -3, -5, -3]
    # A = [1, 2, 3, 4, 5]
    # A = [-2, -3, 4, -1, -2, 1, 5, -3]

    print("using divide and conquer...")
    print("Maximum contiguous sum is",find_maximum_subarray(A, 0, len(A) - 1), "
")

    print("using Kanade Algorithm...")
    print("Maximum contiguous sum is", maxSubArraySum(A, len(A)), "
")

    print("using dynamic programming...")
    MS = DP_maximum_subarray(A)
    print("Maximum contiguous sum is", max(MS), "
")

main()

輸出結(jié)果如下：

using divide and conquer...
Maximum contiguous sum is (7, 10, 43) 

using Kanade Algorithm...
Maximum contiguous sum is 43 

using dynamic programming...
Maximum contiguous sum is 43 

算法導論（第三版） 機械工業(yè)出版社

https://www.geeksforgeeks.org...

https://algorithms.tutorialho...

注意：本人現(xiàn)已開通兩個微信公眾號： 用Python做數(shù)學（微信號為：python_math）以及輕松學會Python爬蟲（微信號為：easy_web_scrape）， 歡迎大家關(guān)注哦~~