問題描述:給定n個整數序列{a1,a2,...,an},求函數f(i,j)=max{0,Σak}(k:連續的從i取到j );
問題即為求已連續子列和的最大值,若果最大值為負數則取0,例如8個數序列{-1,2,-3,4,-2,5, -8,3},那摩最大子序列和為4+(-2)+5=7.
這個問題有四種不同複雜度的演算法,演算法1到四的時間複雜度是O(n 3),O(n2),O(nlogn),O(n);
演算法一:
最直接的方法是窮舉法,列出所有的情況,我們可以設定子序列的左端i和右端j,再利用一層計算出a[i]到a[j]的和.
//最大子列和窮舉法
#include
using namespace std;
int Find_Maxsun (int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_Maxsun(int*a, int n){
int MaxSun = 0, i, j, k;
int NowSum;
for (i = 0; i for (j = 0; j NowSum = 0;
for (k = i; k NowSum += a[k]; /*從a[ i]到a[j]的子序列*/
if (NowSum>MaxSun)
MaxSun = NowSum; /*更新結果*/
}
return MaxSun;
}
很顯然,暴力法使用啦3重for循環,演算法時間複雜度為O(n3),這當然也是一個最笨的演算法,但資料難非常龐大時候,就算是要算到死的節奏,我們可以清楚看到第三層for循環,
j每加一次,子列和都要重頭算一次,那我們為何不去利用j-1的結果呢?也就是說我們將j-1的結果保存下來,在計算j步的結果時候,只需要在j-1步的基礎上再加上a[j],就可以啦,於是有啦算法二。
演算法二:
#include
using namespace std;
int Find_Maxsun2(int*a, int n);
int main(){
int n, i
int;
int main a[1000]; >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_Maxsun2(int*a, int n){
int i, j, NewSum = 0, MaxSum= 0;
for (i = 0 ; i NewSum = 0;
for (j = i; j NewSum += a [j]; /*每次在j-1條件下更新NewSum*/
if (NewSum>MaxSum) /*更新MaxSum*/
MaxSum = NewSum;
}
}
return MaxSum;
}
} return MaxSum;}
}這個演算法
return MaxSum;比1聰明,演算法複雜度是O(n2
),顯然還不是我們想要的複雜度。 演算法三:演算法三使用的是分治法的思想,基本思想不言而喻先分後治,將問題分解為小問題然後在可以總和小問題來解決,我們把原序列一分為二,則最大子序列在左邊,在右邊,或跨越邊界,基本想法如下:第一步:將原序列一分為二,分成左序列和右序列。 第二步:遞歸求出子序列S左和S右。 第三部:從中分線向兩邊掃描,找出跨越中線的最大子序列和S中。 🎜🎜第四步:求得S=max{S左,S中,S右};🎜🎜程式碼實作如下:🎜#include
using namespace std;
int Find_MaxSum3(int*a,int low,int high);
int Max(int a,int b,int c);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_MaxSum3(int*a,int low,int high){
int Find_MaxSum3(int*a,int low,int high){
int MaxSum = 0, MidSum, LeftSum, RightSum,i;
MidSum = 0;
if (low == high){ /*遞歸的終止條件*/
if (a[low] > 0)
return a[low] ;
else
return 0;
}
int mid = (low + high) / 2; //找到分的中點
LeftSum = Find_MaxSum3(a, low, mid); /*遞歸找到左邊序列和*/
RightSum = Find_MaxSum3(a, mid + 1, high); /*遞歸找到右邊序列最大子序列和*/
/*然後可以求中間跨越邊界序列的最大和*/
int NewLeft = 0,Max_BLeorder=0 , NewRight = 0,Max_BorderRight=0;
for (i = mid; i >= low; i--){ /*向左掃描找到最大和*/
NewLeft += a[i];
if (NewLeft > Max_BorderLeft)
Max_BorderLeft = NewLeft;
}
for (i = mid + 1; i NewRight+=a[i];
if (NewRight >= Max_BorderRight)
Max_BorderRight = NewRight;
}
MidSum = Max_BorderRight + Max_BorderLeft;
return Max(LeftSum, MidSum, RightSum); /*回傳的結果*//, aint c){ /*找出3者中最大的數*/
if ( a>= b&&a >= c)
return a;
if (b >= a&&b >= c)
return b;
if (c >= a&&b >= c)
return b;
if (c > = b&&c>=a)
return c;
=2kT(n/2k)+kO(n)=2kT(1)+kO(n)(其中n=2k
)=n+ nlogn=O(nlogn);雖然這個演算法已經非常好啦,但是並不是最快的演算法。 演算法四:演算法四叫做線上處理。意思為,每讀入一個資料就進行及時處理,得到的結果是對於目前讀入的資料都成立,即為在任何位置終止讀入,演算法都可以給出正確的解,邊讀邊解。
#include
using namespace std;
int Find_MaxSum4(int*a, int n);
int main(){
int n, i;
int a[100]; cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_MaxSum4(int*a, int n){
int i, NewSum = 0, MaxSum = 0;
for (i = 0; i NewSum += a[i]; /*目前子序列和*/
if (MaxSum MaxSum = NewSum; /*更新最大子序列和*/
if (NewSum NewSum = 0;
}
return MaxSum;
}
以上就介紹了最大子序列和演算法分析,包括了方面的內容,希望對PHP教程有興趣的朋友有幫助。