656
技術社區[雲棲]
動態規劃經典題目：最大連續子序列和
最大連續子序列和問題
給定k個整數的序列{N1,N2,...,Nk }，其任意連續子序列可表示為{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= k。最大連續子序列是所有連續子序中元素和最大的一個，例如給定序列{ -2, 11, -4, 13, -5, -2 }，其最大連續子序列為{11,-4,13}，最大連續子序列和即為20。
注：為方便起見，如果所有整數均為負數，則最大子序列和為0。
解決這樣一個問題是一個很有趣的過程，我們可以嚐試著從複雜度比較高的算法一步一步地推出複雜度較低的算法。
算法一：
時間複雜度：O(N^3)
其代碼：
int MaxSubSequence(const int A[], int N){
int ThisSum,MaxSum,i,j,k;
MaxSum = 0;
for(i=0;i<N;i++)
{
for(j=i;j<N;j++)
{
ThisSum = 0;
for(k=i;k<=j;k++)
{
ThisSum += A[k];
}
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}
對於此種算法，其主要方法是窮舉法，即求出該序列所有子序列的序列和，然後取最大值即可。
算法二：
時間複雜度：O(N^2)
其代碼：
int MaxSubSequence(const int A[], int N){
int ThisSum,MaxSum,i,j;
MaxSum = 0;
for(i=0;i<N;i++)
{
ThisSum = 0;
for(j=i;j<N;j++)
{
ThisSum += A[j];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}
對於這種方法，歸根究底還是屬於窮舉法，其間接地求出了所有的連續子序列的和，然後取最大值即可。
那麼，這裏，我們需要對比一下前麵兩種算法，為什麼同樣都是窮舉法，但算法一的時間複雜度遠高於算法二的時間複雜度？
算法二相較於算法一，其優化主要體現在減少了很多重複的操作。
對於A-B-C-D這樣一個序列，
算法一在計算連續子序列和的時候，其過程為：
A-B、A-C、A-D、B-C、B-D、C-D
而對於算法二，其過程為：
A-B、A-C、A-D、B-C、B-D、C-D
其過程貌似是一樣的，但是算法一的複雜就在於沒有充分利用前麵已經求出的子序列和的值。
舉個例子，算法一在求A-D連續子序列和的值時，其過程為A-D = A-B + B-C + C-D；
而對於算法二，A-D連續子序列和的求值過程為A-D = A-C+C-D；
這樣，算法二充分利用了前麵的計算值，這樣就大大減少了計算子序列和的步驟。
算法三：遞歸法（分治法）
時間複雜度：O(NlogN)
易知，對於一數字序列，其最大連續子序列和對應的子序列可能出現在三個地方。或是整個出現在輸入數據的前半部（左），或是整個出現在輸入數據的後半部（右），或是跨越輸入數據的中部從而占據左右兩半部分。前兩種情況可以通過遞歸求解，第三種情況可以通過求出前半部分的最大和（包含前半部分的最後一個元素）以及後半部分的最大和（包含後半部分的第一個元素）而得到，然後將這兩個和加在一起即可。
其實現代碼為：
int MaxSubSequence(const int A[],int N)
{
return MaxSubSum(A,0,N-1);
}
static int MaxSubSum(const int A[], int Left, int Right)
{
int MaxLeftSum,MaxRightSum;
int MaxLeftBorderSum,MaxRightBorderSum;
int LeftBorderSum,RightBorderSum;
int Center,i;
if(Left == Right)
{
if(A[Left] > 0)
return A[Left];
else
return 0;
}
Center = (Left + Right)/2;
MaxLeftSum = MaxSubSequence(A,Left,Center);
MaxRightSum = MaxSubSequence(A,Center+1,Right);
MaxLeftBorderSum = 0;
LeftBorderSum = 0;
for(i = Center;i >= Left;i--)
{
LeftBorderSum += A[i];
if(LeftBorderSum > MaxLeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
}
MaxRightBorderSum = 0;
RightBorderSum = 0;
for(i = Center+1;i <= Right;i++)
{
RightBorderSum += A[i];
if(RightBorderSum > MaxRightBorderSum)
MaxRightBorderSum = RightBorderSum;
}
return Max(MaxLeftSum,MaxRightSum,MaxLeftBorderSum + MaxRightBorderSum);
}
int Max(int a, int b, int c)
{
if(a>b&&a>c)
return a;
else if(b>a&&b>c)
return b;
else
return c;
}
現在對上麵的代碼進行相關說明：
Center變量所確定的值將處理序列分割為兩部分，一部分為Center前半部，一部分為Center+1後半部。
在上文，我們提到，最大連續子序列的出現位置有三種情況。
對於前兩種情況，我們根據遞歸特性，可以得到：
MaxLeftSum = MaxSubSequence(A,Left,Center); MaxRightSum = MaxSubSequence(A,Center+1,Right);而對於第三種情況，我們需要先求出前半部包含最後一個元素的最大子序列：
MaxLeftBorderSum = 0;
LeftBorderSum = 0;
for(i = Center;i >= Left;i--)
{
LeftBorderSum += A[i];
if(LeftBorderSum > MaxLeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
}
然後，再求出後半部包含第一個元素的最大子序列：
MaxRightBorderSum = 0;
RightBorderSum = 0;
for(i = Center+1;i <= Right;i++)
{
RightBorderSum += A[i];
if(RightBorderSum > MaxRightBorderSum)
MaxRightBorderSum = RightBorderSum;
} 最後，我們隻需比較這三種情況所求出的最大連續子序列和，取最大的一個，即可得到需要求解的答案。return Max(MaxLeftSum,MaxRightSum,MaxLeftBorderSum + MaxRightBorderSum);我們在介紹這個算法的開始，就已經提到了其時間複雜度，現在做一個推導：
令T(N)是求解大小為N的最大連續子序列和問題所花費的時間。
當N==1時，T(1) = 1；
當N>1時，T(N) = T(N/2) + O(N)；
有數學推導公式，我們可以得到：
T(N) = NlogN + N =O(NlogN)。
算法四：動態規劃法
時間複雜度：O(N)
終於到了動態規劃的部分了，這麼一步一步走來，感受到了算法的無窮魅力。那麼如何用動態規劃來處理這個問題？
首先，我們重溫將一個問題用動態規劃方法處理的準則：
“最優子結構”、“子問題重疊”、“邊界”和“子問題獨立”。
在本問題中，我們可以將子序列與其子子序列進行問題分割。
最後得到的狀態轉移方程為：
MaxSum[i] = Max{ MaxSum[i-1] + A[i], A[i]};
在這裏，我們不必設置數組MaxSum[]。
代碼實現：
int MaxSubSequence(const int A[], int N)
{
int ThisSum,MaxSum,j;
ThisSum = MaxSum =0;
for(j = 0;j < N;j++)
{
ThisSum += A[j];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
else if(ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}
在本代碼實現中，ThisSum持續更新，同時整個過程，隻對數據進行了一次掃描，一旦A[i]被讀入處理，它就不再需要被記憶。（聯機算法）
小結：
整個過程是一個思想的選擇問題，從最初的窮舉法，到分治法，再到動態規劃法。算法設計思想的靈活選擇是處理一個實際問題的關鍵。
最後更新：2017-04-03 05:39:50