最大子列和問題

問題描述：

給定K個整數組成的序列{ N₁, N₂, ..., N_K?}，“連續子列”被定義為{ N_i, N_i+1, ..., N_j?}，其中 1 <= i <= j <= K。“最大子列和”則被定義為所有連續子列元素的和中最大者。例如給定序列{ -2, 11, -4, 13, -5, -2 }，其連續子列{ 11, -4, 13 }有最大的和20。現要求你編寫程序，計算給定整數序列的最大子列和。

輸入格式：

輸入第1行給出正整數 K (<= 100000)；第2行給出K個整數，其間以空格分隔。

輸出格式：

在一行中輸出最大子列和。如果序列中所有整數皆為負數，則輸出0。

輸入樣例： 6 -2 11 -4 13 -5 -2 輸出樣例： 20

完整代碼：（實現的為算法4，下面有詳解）

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include <iostream>
//using namespace std;
int MaxSubsequenceSum(int a[],int n);
int _tmain(int argc, _TCHAR* argv[])
{
int n = 0;
int sum = 0;
scanf("%d",&n);
int *a = new int[n];
for(int i = 0;i<n;i++)
scanf("%d",&a[i]);
sum = MaxSubsequenceSum(a,n);
std::cout<<sum<<std::endl;
system("pause");
return 0;

}

int MaxSubsequenceSum(int a[],int N)
{
int Thissum,Maxsum,i;
Thissum =0;
Maxsum =0;
int l = 0;
for(i = 0;i<N;i++)
{
Thissum += a[i];
if(Thissum > Maxsum)
{
Maxsum = Thissum;
}
else if (Thissum < 0)
{
Thissum =0;
l++;
}
}
if(l == N)
{
return 0;
}
else
return Maxsum;
}

算法一：

?

?

?int MaxSubsequenceSum(int a[],int N)
?{
??int ThisSum,MaxSum,i,j,k;
? ? ? ?MaxSum=0;

? int l =0;
?????for (i=0;i<10;i++)
? ? ? ? for(j=i;j<10;j++)
? ? ? ? ?{
? ? ? ? ? ?ThisSum=0;
? ? ? ? ? ?for (k=i;k<=j;k++)
? ? ? ? ? ? ? ?ThisSum+=a[k];??
? ? ? ? ? if(ThisSum>MaxSum)
? ? ? ? ? MaxSum=ThisSum;
????????}

if(l == N)
{
return 0;
}
else
return Maxsum;

?}
我們來分析一下這個程序,首先這個程序肯定是完全正確的。運行時間為O(N3)，這完全取決于第5行和第六行，第六行有一個含于三重嵌套for循環中的O(1)語句組成。第2行的循環大小為N。

第二個循環大小為N-i，他可能要小，但也可能是N。我們必須假設最壞的情況，而這可能會使得最終的界有些大。第三個循環的大小為j-i+1，我們也要假設它的大小為N。為此總數為O(1*N*N*N)=O(N3)。語句1總的開銷只是O(1),而語句7和8總共開銷也只不過O(N2),因為他們只是兩層循環內部的簡單表達式。

我們在將結合各個語句的開銷大小，更精確的分析出答案是θ(N3),而上面的估計高出個因子6（不過這并不影響，因為常數不影響數量級）。下面是具體計算的過程：

精確分析由這個式子得出

?

最后答案是(N3+3*N2+2*N)/6

顯然這個算法過于消耗時間在第5行和第6行上的計算過分的耗時了。現在有一種改進的算法2

我們可以通過撤除一個for循環來避免立方運行時間。

下面是這個算法的函數：

算法2：

int MaxSubsequenceSum(int a[],int N)
{
?int ThisSum,MaxSum,i,j;
?MaxSum=0;

int l = 0;

?for (i=0;i<10;i++)
?{?
??ThisSum=0;
??for(j=i;j<10;j++)
??{
???
???
???ThisSum+=A[j];??
???if(ThisSum>MaxSum)
???MaxSum=ThisSum;
??}
?}

if(l == N)
{
return 0;
}
else
return Maxsum;

}????

這個算法顯然是O(N2)的還有一種更簡單的算法其相對時間復雜度為O(NlogN)解法，現在我們來描述它。

這個算法可以體現遞歸算法的優勢，該方法采用一種“分治”策略。其想法是吧問題分成兩個大致相等的子問題，然后遞歸地對它們求解，這是分部分。“治”階段將兩個子問題的解合并到一起并可能再做些少量的附加工作，最后得到整個問題的解。

在這個問題中，最大子序列和可能出現在3個地方。或者整個出現在輸入數據的左半部分，或者整個出現在右半部分。或者跨越輸入數據的中部從而占據左右兩半部分。前兩種情況可以遞歸求解。第三種情況的最大和可以通過求出前半部分的最大和（包含前半部分的最后一個元素）以及后半部分的最大和（包含后半部分的第一個元素）而得到。然后將這兩個和加在一起。

算法3：
static int MaxSubSum(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=MaxSubSum(A,Left,Center);
??MaxRightSum=MaxSubSum(A,Center+1,Right);

?MaxLeftBorderSum=0;LeftBorderSum=0;
??for (i=Center;i>=Left;i--)
?{
??LeftBorderSum+=a[i];
??if (LeftBorderSum>MaxLeftBorderSum)
??
???MaxLeftBorderSum=RightBorderSum;
??
?}
???MaxRightBorderSum=0;RightBorderSum=0;
?????for (i=Center+1;i<=Right;i++)
???{
????RightBorderSum+=a[i];
????if (RightBorderSum>MaxRightBorderSum)
????????MaxRightBorderSum=RightBorderSum;???????
???}
???return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);

}

int MaxSubsequenceSum(const int a[],int N)
{
?return MaxSubSum(a,0,N-1);
}

遞歸過程調用的一般形式是傳遞輸入的數組以及左邊界和右邊界，它們界定額數組要被處理的部分。單行驅動程序通過傳遞數組以及邊界0和N-1而啟動該過程。

第一行至第四行處理基準情況。如果Left==Right，那么只有一個元素，并且當該元素非負時它就是最大和子序列。Left>Right的情況是不可能出現的，除非N是負數（不過程序中的小擾動有可能致使這種混亂產生）。第六行和第七行執行的兩次遞歸調用。我們可以看到，遞歸調用總是對于小于原問題的問題進行，但程序總的小擾動有可能破換這個特性。第八行至第十二行以及第十三行至第十七行計算達到中間分界處的兩個最大和的和數。這兩個最大和的和為擴展到左右兩邊的最大和。偽例程Max3返回這三個有可能的最大和中的最大者。

顯然，編程時，算法3比前面兩種算法需要更多的精力。然而，程序短并不意味著程序號。正如我們在前面顯示算法運行時間的表中已看到，除最小輸入外，該算法比前面兩個算法明顯要快。

最后一種算法是最為有效的算法，

算法4:

int MaxSubsequenceSum(int a[],int N)
{
?????int ThisSum,MaxSum,j;

? ? ?int l = 0;
????ThisSum=MaxSum=0;

????for(j=0;j<N;j++)
????{
???????????ThisSum+=a[j];
?????if(ThisSum>MaxSum)
?????MaxSum=ThisSum;
?????else if(ThisSum<0)
?????ThisSum=0;
????}

if(l == N)
{
return 0;
}
else
return Maxsum;

}

算法4的時間復雜度為O(N),這是線性的。該算法的有點是，它只對數據進行一次掃描，一旦A[i]被讀入處理，它就不再需要被記憶。因此，如果數組在磁盤或者磁帶上，它就可以被順序讀入，在主存中不必儲存數組的任何部分。不僅如此，在任意時刻，算法都能對它已經讀入的數據給出子序列問題的正確答案。具有這種特性的算法叫做聯機算法.僅需要常量空間并以線性時間運行的聯機算法幾乎是完美的算法。

轉載于:https://www.cnblogs.com/Logic09/p/4145886.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的C++求解最大子序列和问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。