問題描述：給定n個整數(shù)序列{a1,a2,...,an},求函數(shù)f(i,j)=max{0,Σak}(k:連續(xù)的從i取到j);

問題即為求已連續(xù)子列和的最大值，若果最大值為負數(shù)則取0，比如8個數(shù)序列{-1,2，-3,4，-2,5，-8,3}，那摩最大子序列和為4+（-2）+5=7.

這個問題有四種不同復雜度的算法，算法1到四的時間復雜度是O(n3),O(n2),O(nlogn),O(n);

算法一：

最直接的方法是窮舉法，列出所有的情況，我們可以設定子序列的左端i和右端j,再利用一層計算出a[i]到a[j]的和.

//最大子列和窮舉法#include<iostream>using namespace std;int Find_Maxsun(int*a, int n);int main(){int n, i;int a[100];cin >> n;cout << "Pleace Input The " << n << "Number:" << endl;for (i = 0; i < n; i++)cin >> a[i];cout<<Find_Maxsun(a, n) << endl;return 0;}int Find_Maxsun(int*a, int n){int MaxSun = 0, i, j, k;int NowSum;for (i = 0; i < n; i++) /*子序列左端*/for (j = 0; j < n; j++){ /*子序列右端*/NowSum = 0;for (k = i; k <= j; k++) NowSum += a[k]; /*從a[i]到a[j]的子序列*/if (NowSum>MaxSun)MaxSun = NowSum; /*更新結果*/}return MaxSun;}

很顯然，暴力法使用啦3重for循環(huán)，算法時間復雜度為O(n3)，這當然也是一個最笨的算法，但數(shù)據(jù)難非常龐大時候，哪怕是要算到死的節(jié)奏，我們可以清楚看到第三層for循環(huán)，

j每加一次，子列和都要重頭算一次，那我們?yōu)楹尾蝗ダ胘-1的結果呢？也就是說我們將j-1的結果保存下來，在計算j步的結果時候，只需要在j-1步的基礎上再加上a[j]，就可以啦，于是有啦算法二。

算法二：

#include<iostream>using namespace std;int Find_Maxsun2(int*a, int n);int main(){int n, i;int a[100];cin >> n;cout << "Pleace Input The " << n << " Number:" << endl;for (i = 0; i < n; i++)cin >> a[i];cout << Find_Maxsun2(a, n) << endl;return 0;}int Find_Maxsun2(int*a, int n){int i, j, NewSum = 0, MaxSum= 0;for (i = 0; i < n; i++){ /*為序列的左邊端點*/NewSum = 0;for (j = i; j < n; j++){ /*j為系列右端點*/NewSum += a[j]; /*每一次在j-1條件下更新NewSum*/if (NewSum>MaxSum) /*更新MaxSum*/ MaxSum = NewSum;}}return MaxSum;}

這個算法比1聰明，算法復雜度是O(n2)，顯然還不是我們想要的復雜度。

算法三：

算法三使用的是分治法的思想，基本思想不言而喻先分后治，將問題分解為小問題然后在可以總和小問題來解決，我們把原序列一分為二，那么最大子序列在左邊，在右邊，或者跨越邊界，基本思路如下：

第一步：將原序列一分為二，分成左序列和右序列。

第二步：遞歸求出子序列S左和S右。

第三部：從中分線向兩邊掃描，找出跨越中線的最大子序列和S中。

第四步：求得S=max{S左，S中，S右}；

代碼實現(xiàn)如下：

#include<iostream>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 << "Pleace Input The " << n << " Number:" << endl;for (i = 0; i < n; i++)cin >> a[i];cout << Find_MaxSum3(a,0,n-1) << endl;return 0;}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];elsereturn 0;}int mid = (low + high) / 2; //找到分的中點LeftSum = Find_MaxSum3(a, low, mid); /*遞歸找到左邊序列最大和*/RightSum = Find_MaxSum3(a, mid + 1, high); /*遞歸找到右邊序列最大子序列和*//*然后可以求中間跨越邊界序列的最大和*/int NewLeft = 0,Max_BorderLeft=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 <= high; i++){ /*向右掃描找到最大子序列和*/NewRight+=a[i];if (NewRight >= Max_BorderRight)Max_BorderRight = NewRight;}MidSum = Max_BorderRight + Max_BorderLeft;return Max(LeftSum, MidSum, RightSum); /*返回治的結果*/}int Max(int a, int b, int c){ /*找出3者中最大的數(shù)*/if ( a>= b&&a >= c)return a;if (b >= a&&b >= c)return b;if (c >= b&&c>=a)return c;}

我們來算一算這個算法時間復雜度：

T(1)=1;

T(n)=2T(n/2)+O(n);

=2kT(n/2k)+kO(n)=2kT(1)+kO(n)（其中n=2k）=n+nlogn=O(nlogn);

雖然這個算法已經(jīng)非常好啦，但是并不是最快的算法。

算法四：

算法四叫做在線處理。意思為，每讀入一個數(shù)據(jù)就進行及時處理，得到的結果是對于當前讀入的數(shù)據(jù)都成立，即為在任何位置終止讀入，算法都可以給出正確的解，邊讀邊解。

#include<iostream>using namespace std;int Find_MaxSum4(int*a, int n);int main(){int n, i;int a[100];cin >> n;cout << "Pleace Input The " << n << " Number:" << endl;for (i = 0; i < n; i++)cin >> a[i];cout << Find_MaxSum4(a,n) << endl;return 0;}int Find_MaxSum4(int*a, int n){int i, NewSum = 0, MaxSum = 0;for (i = 0; i < n; i++){NewSum += a[i]; /*當前子序列和*/if (MaxSum < NewSum)MaxSum = NewSum; /*更新最大子序列和*/if (NewSum < 0) /*小于0則拋棄*/ NewSum = 0;}return MaxSum;}

這種算法是將讀入的數(shù)據(jù)一個個掃描一遍，只有一個for循環(huán)，解決同一個問題算法差別大，在于一個竅門，讓計算機記住一些關鍵的中間結果，避免重復計算。