問(wèn)題簡(jiǎn)介
??本文將介紹計(jì)算機(jī)算法中的經(jīng)典問(wèn)題——最大子數(shù)組問(wèn)題（maximum subarray problem）。所謂的最大子數(shù)組問(wèn)題甲抖，指的是：給定一個(gè)數(shù)組A，尋找A的和最大的非空連續(xù)子數(shù)組。比如笔诵，數(shù)組 A = [-2, -3, 4, -1, -2, 1, 5, -3]， 最大子數(shù)組應(yīng)為[4, -1, -2, 1, 5],其和為7姑子。
??首先乎婿，如果A中的元素全部為正（或非負(fù)數(shù)），則最大子數(shù)組就是它本身街佑；如果A中的元素全部為負(fù)谢翎，則最大子數(shù)組就是第一個(gè)元素組成的數(shù)組。以上兩種情形是平凡的沐旨，那么森逮，如果A中的元素既有正數(shù)，又有負(fù)數(shù)磁携，則該如何求解呢褒侧？本文將介紹該問(wèn)題的四種算法，并給出后面三種算法的Python語(yǔ)言實(shí)現(xiàn)，解決該問(wèn)題的算法如下：
- 暴力求解
- 分治法
- Kadane算法
- 動(dòng)態(tài)規(guī)劃法
??下面就這四種算法做詳細(xì)介紹闷供。
暴力求解
??假設(shè)數(shù)組的長(zhǎng)度為n烟央，暴力求解方法的思路是很簡(jiǎn)單的，就是將子數(shù)組的開(kāi)始坐標(biāo)和結(jié)束坐標(biāo)都遍歷一下这吻，這樣共有n(n-1)/2中組合方式吊档，再考慮這所有組合方式中和最大的情形即可。
??該算法的運(yùn)行時(shí)間為O(n^2),效率是很低的唾糯。那么怠硼，還有其它高效的算法嗎？
分治法
??分治法的基本思想是將問(wèn)題劃分為一些子問(wèn)題移怯，子問(wèn)題的形式與原問(wèn)題一樣香璃，只是規(guī)模更小，遞歸地求解出子問(wèn)題舟误，如果子問(wèn)題的規(guī)模足夠小葡秒，則停止遞歸，直接求解嵌溢，最后將子問(wèn)題的解組合成原問(wèn)題的解眯牧。
??對(duì)于最大子數(shù)組，我們要尋求子數(shù)組A[low...high]的最大子數(shù)組赖草。令mid為該子數(shù)組的中央位置学少，我們考慮求解兩個(gè)子數(shù)組A[low...mid]和A[mid+1...high]。A[low...high]的任何連續(xù)子數(shù)組A[i...j]所處的位置必然是以下三種情況之一：
- 完全位于子數(shù)組A[low...mid]中,因此 low <= i <= j <= mid.
- 完全位于子數(shù)組A[mid+1...high]中,因此mid< i <= j <= high.
- 跨越了中點(diǎn)秧骑，因此low <= i <= mid < j <= high.
因此版确，最大子數(shù)組必定為上述3種情況中的最大者。對(duì)于情形1和情形2乎折，可以遞歸地求解绒疗，剩下的就是尋找跨越中點(diǎn)的最大子數(shù)組。
??任何跨越中點(diǎn)的子數(shù)組都是由兩個(gè)子數(shù)組A[i...mid]和A[mid+1...j]組成骂澄，其中l(wèi)ow <= i <= mid且mid < j <= high.因此吓蘑，我們只需要找出形如A[i...mid]和A[mid+1...j]的最大子數(shù)組，然后將其合并即可坟冲，這可以在線性時(shí)間內(nèi)完成士修。過(guò)程FIND-MAX-CROSSING-SUBARRAY接收數(shù)組A和下標(biāo)low、mid和high作為輸入樱衷，返回一個(gè)下標(biāo)元組劃定跨越中點(diǎn)的最大子數(shù)組的邊界，并返回最大子數(shù)組中值的和酒唉。其偽代碼如下：
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我們可以找到跨越中點(diǎn)的最大子數(shù)組矩桂，于是，我們也可以設(shè)計(jì)求解最大子數(shù)組問(wèn)題的分治算法了，其偽代碼如下：
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)
??顯然這樣的分治算法對(duì)于初學(xué)者來(lái)說(shuō)侄榴，有點(diǎn)難度非洲，但是熟能生巧, 多學(xué)多練也就不難了辅辩。該分治算法的運(yùn)行時(shí)間為O(n*logn).
Kadane算法
??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算法的簡(jiǎn)單想法就是尋找所有連續(xù)的正的子數(shù)組（max_ending_here就是用來(lái)干這事的），同時(shí)，記錄所有這些連續(xù)的正的子數(shù)組中的和最大的連續(xù)數(shù)組申尼。每一次我們得到一個(gè)正數(shù)，就將它與max_so_far比較螺戳，如果它的值比max_so_far大踏堡，則更新max_so_far的值。
動(dòng)態(tài)規(guī)劃法
?? 用MS[i]表示最大子數(shù)組的結(jié)束下標(biāo)為i的情形恒水，則對(duì)于i-1会放，有：
????????????MS[i] = max {MS[i-1], A[i]}.
這樣就有了一個(gè)子結(jié)構(gòu)，對(duì)于初始情形钉凌，MS[1]=A[1].遍歷i, 就能得到MS這個(gè)數(shù)組咧最，其最大者即可最大子數(shù)組的和。
總結(jié)
?? 可以看到以上四種算法御雕，每種都有各自的優(yōu)缺點(diǎn)矢沿。對(duì)于暴力求解方法，想法最簡(jiǎn)單酸纲，但是算法效率不高捣鲸。Kanade算法簡(jiǎn)單高效，但是不易想到福青。分治算法運(yùn)行效率高摄狱，但其分支過(guò)程的設(shè)計(jì)較為麻煩。動(dòng)態(tài)規(guī)劃法想法巧妙无午，運(yùn)行效率也高媒役，但是沒(méi)有普遍的適用性。
Python程序
?? 下面將給出分治算法宪迟，Kanade算法和動(dòng)態(tài)規(guī)劃法來(lái)求解最大子數(shù)組問(wèn)題的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), '\n')
print('using Kanade Algorithm...')
print("Maximum contiguous sum is", maxSubArraySum(A, len(A)), '\n')
print('using dynamic programming...')
MS = DP_maximum_subarray(A)
print("Maximum contiguous sum is", max(MS), '\n')
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
參考文獻(xiàn)
- 算法導(dǎo)論（第三版） 機(jī)械工業(yè)出版社
- https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
- https://algorithms.tutorialhorizon.com/dynamic-programming-maximum-subarray-problem/
注意：本人現(xiàn)已開(kāi)通兩個(gè)微信公眾號(hào)： 用Python做數(shù)學(xué)（微信號(hào)為：python_math）以及輕松學(xué)會(huì)Python爬蟲(chóng)（微信號(hào)為：easy_web_scrape）， 歡迎大家關(guān)注哦~~
