一道算法題，看看大家的思路（續）

　　現再将題目複述一遍：

　　題目描述：有31，-41，59，26，-53，58，97，-93，-23，84十個數。SUM（N，M）表示從第N個數到到第M個數的和。例如：SUM（2，3）=-41+59=18。問：最大的和是多少？對應的N和M是多少？

　　先不管N和M的計算，直接計算SUM，看看用什麼算法。

　　算法一：直接周遊窮舉，求出SUM。代碼如下：

　　Public Function MaxSum1() As Integer

　　　　Dim i As Integer, j As Integer, k As Integer, _

　　　　Sum As Integer, Maximum As Integer = Integer.MinValue

　　　　For i = 0 To A.GetUpperBound(0)

　　　　　　For j = i To A.GetUpperBound(0)

　　　　　　　　Sum = 0

　　　　　　　　For k = i To j

　　　　　　　　　　Sum += A(k)

　　　　　　　　　　If Sum > Maximum Then Maximum = Sum

　　　　　　　　Next

　　　　　　Next

　　　　Next

　　　　Return Maximum

　　End Function

　　這個代碼最容易了解，但是效率最低，算法的複雜度為O(N3)

　　算法二，在算法一的基礎上改進，因為SUM（N，M）=SUM（N，M-1）+A（M），基于這個原理，将上述代碼中的最裡面的一層循環去掉。

　　Public Function MaxSum2() As Integer

　　　　Dim i As Integer, j As Integer, Sum As Integer, _

　　　　　 Maximum As Integer = Integer.MinValue

　　　　　　Sum = 0

　　　　　　　　Sum += A(j)

　　　　　　　　If Sum > Maximum Then Maximum = Sum

　　這個代碼也很容易了解，算法執行效率有明顯的提高，算法的複雜度為O(N2)，但還不夠。

　　算法三：

　　考慮數組第一個元素A（0）和最大和的一段數組A（N），……，A（M）。他們之間有如下關系：

　　1、當0=N=M時，元素A（0）本身構成最大和的一段

　　2、當0=N<M時，最大和的一段以A（0）開始

　　3、當0<N時，A（0）和最大和一段沒有什麼關系。

　　假設數組有N個元素，分别為A（0），A（1），……，A（N-1）

　　并且我還知道從A（1）到A（N-1）的最大和為All（1），從A（1）到A（N-1）中包含A（1）的最大和為Start（1）

　　那麼，從A（0）到A（N-1）的最大和All（0）就一定有下面的關系式：

　　All（0）=Max｛A（0），A（0）+Start（1），All（1）｝

　　而Start（0）有如下的關系式：

　　Start（0）=Max｛A（0），A（0）+Start（1）｝

　　看了上面的分析，将N個元素的問題就轉化為了N-1個元素的問題。這是我想到了遞推。（書上以及很多其他的部落格說是動态規劃，我沒有了解，個人比較愚鈍）

　　将上面的式子整理一下，建立好遞推關系：

　　Start（i）=Max｛A（i），A（i）+Start（i+1）｝

　　All（i）=Max｛Start（i），All（i+1）｝

　　代碼如下：

　　Public Function Max(ByVal X As Integer, ByVal Y As Integer) As Integer

　　　　Return IIf(X > Y, X, Y)

　　Public Function MaxSum3() As Integer

　　　　Dim i As Integer, Start() As Integer, All() As Integer

　　　　ReDim Start(A.GetUpperBound(0))

　　　　ReDim All(A.GetUpperBound(0))

　　　　Start(A.GetUpperBound(0)) = A(A.GetUpperBound(0))

　　　　All(A.GetUpperBound(0)) = A(A.GetUpperBound(0))

　　　　For i = A.GetUpperBound(0) - 1 To 0 Step -1

　　　　　　Start(i) = Max(A(i), A(i) + Start(i + 1))

　　　　　　All(i) = Max(Start(i), All(i + 1))

　　　　Return All(0)

　　這個算法的效率很高，算法複雜度為O(N)，但是引用了兩個數組。仔細觀察兩個數組的使用情況，發現其實隻要使用兩個變量就完全可以了，下面是改進的代碼。

　　Public Function MaxSum4() As Integer

　　　　Dim i As Integer, Start As Integer, All As Integer

　　　　Start = A(A.GetUpperBound(0))

　　　　All = A(A.GetUpperBound(0))

　　　　　　Start = Max(A(i), A(i) + Start)

　　　　　　All = Max(Start, All)

　　　　Return All

　　将上面的代碼，仔細分析一下可以發現：

　　Start=Max（A（i），A（i）+Start）

　　可以改寫為：

　　If Start<0 Then

　　　　Start=A（i）

　　Else

　　　　Start=A（i）+Start

　　End If

　　繼而可以改寫為

　　If Start<0 Then Start=0

　　Start=A（i）+Start

　　而All = Max(Start, All)可以改寫為

　　If Start>All Then All=Start

　　故上面的代碼，可以改寫為一個函數，減少系統的開銷

　　Public Function MaxSum5() As Integer

　　　　　　If Start < 0 Then Start = 0

　　　　　　Start += A(i)

　　　　　　If Start > All Then All = Start

　　至此，代碼效率高，又簡潔明了。唯一的缺憾是從數組的最後一個倒推，下面的代碼改成正推

　　Public Function MaxSum6() As Integer

　　　　Start = A(0)

　　　　All = A(0)

　　　　For i = 1 To A.GetUpperBound(0)

　　以上的推導過程就是為了求出一個最大和，沒有求出具體的下标。關于下标的計算，留待後文詳述。

　　代碼格式修正于2012年1月6日