問題描述：
輸入一組整數，求出這組數字子序列和中最大值。也就是只要求出最大子序列的和，不必求出最大的那個序列。例如：
序列：-2 11 -4 13 -5 -2，則最大子序列和為20。
序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，則最大子序列和為16。
算法一：
//窮舉法，復雜度O(n^3) 最容易想到也是最簡單的算法
[cpp]
<SPAN style="FONT-SIZE: 14px">long maxSubSum1(const vector<int>&a)
{
long maxSum= 0;
for (int i= 0; i < a.size(); i++)
{
for (int j= i; j < a.size(); j++)
{
long thisSum= 0;
for (int k= i; k <= j; k++)
{
thisSum+= a[k];
}
if (thisSum> maxSum)
maxSum= thisSum;
}
}
return maxSum;
} </SPAN>
long maxSubSum1(const vector<int>&a)
{
long maxSum= 0;
for (int i= 0; i < a.size(); i++)
{
for (int j= i; j < a.size(); j++)
{
long thisSum= 0;
for (int k= i; k <= j; k++)
{
thisSum+= a[k];
}
if (thisSum> maxSum)
maxSum= thisSum;
}
}
return maxSum;
}
這是一個O(N^3) 的算法，算法本身很容易理解，而且很直觀的感覺做了很多無用操作。例如：i = 0, j = 3時，會計算a[0] +a[1] +…+ a[3]；而當i = 0, j = 4時候又會計算a[0]+ a[1] +…a[4]。
算法二：
通過撤出一個for循環來避免三次時間。
//也是窮舉法，不過減去了上面的一些不必要操作O(n^2)
[cpp]
<SPAN style="FONT-SIZE: 14px">long maxSubSum2(const vector<int>&a)
{
long maxSum= 0;
for (int i= 0; i < a.size(); i++)
{
long thisSum= 0;
for (int j= i; j < a.size(); j++)
{
thisSum+= a[j];
if (thisSum> maxSum)
maxSum= thisSum;
}
}
return maxSum;
}</SPAN>
long maxSubSum2(const vector<int>&a)
{
long maxSum= 0;
for (int i= 0; i < a.size(); i++)
{
long thisSum= 0;
for (int j= i; j < a.size(); j++)
{
thisSum+= a[j];
if (thisSum> maxSum)
maxSum= thisSum;
}
}
return maxSum;
}
這是一個非常直觀的窮舉法（比上面的分析還有簡單些），而且沒有多余重復的操作，復雜度為O(N^2) 。其中，thisSum表示a[i] + a[i+1] + … + a[j-1]。
算法三：
對這個問題，有一個相對復雜的O(NlogN)的解法，就是使用遞歸。如果要是求出序列的位置的話，這將是最好的算法了（因為我們後面還會有個O(N)的算法，但是不能求出最大子序列的位置）。該方法我們采用“分治策略”（divide-and-conquer）。
在我們例子中，最大子序列可能在三個地方出現，或者在左半部，或者在右半部，或者跨越輸入數據的中部而占據左右兩部分。前兩種情況遞歸求解，第三種情況的最大和可以通過求出前半部分最大和（包含前半部分最後一個元素）以及後半部分最大和（包含後半部分的第一個元素）相加而得到。
//遞歸法，復雜度是O(nlogn)
[cpp]
<SPAN style="FONT-SIZE: 14px">long maxSumRec(const vector<int>&a, int left, int right)
{
if (left== right)
{
if (a[left]> 0)
return a[left];
else
return 0;
}
int center= (left + right) / 2;
long maxLeftSum= maxSumRec(a, left, center);
long maxRightSum= maxSumRec(a, center+1, right);
//求出以左邊對後一個數字結尾的序列最大值
long maxLeftBorderSum= 0, leftBorderSum = 0;
for (int i= center; i >= left; i--)
{
leftBorderSum+= a[i];
if (leftBorderSum> maxLeftBorderSum)
maxLeftBorderSum= leftBorderSum;
}
//求出以右邊對後一個數字結尾的序列最大值
long maxRightBorderSum= 0, rightBorderSum = 0;
for (int j= center+1; j <= right; j++)
{
rightBorderSum+= a[j];
if (rightBorderSum> maxRightBorderSum)
maxRightBorderSum= rightBorderSum;
}
return max3(maxLeftSum,maxRightSum,
maxLeftBorderSum+ maxRightBorderSum);
}
long maxSubSum3(const vector<int>&a)
{
return maxSumRec(a,0, a.size()-1);
}
另外max3(long,long,long)表示求三個long中的最大值：
//求出三個long中的最大值
long max3(long a, long b, long c)
{
if (a< b)
{
a= b;
}
if (a> c)
return a;
else
return c;
}</SPAN>
long maxSumRec(const vector<int>&a, int left, int right)
{
if (left== right)
{
if (a[left]> 0)
return a[left];
else
return 0;
}
int center= (left + right) / 2;
long maxLeftSum= maxSumRec(a, left, center);
long maxRightSum= maxSumRec(a, center+1, right);
//求出以左邊對後一個數字結尾的序列最大值
long maxLeftBorderSum= 0, leftBorderSum = 0;
for (int i= center; i >= left; i--)
{
leftBorderSum+= a[i];
if (leftBorderSum> maxLeftBorderSum)
maxLeftBorderSum= leftBorderSum;
}
//求出以右邊對後一個數字結尾的序列最大值
long maxRightBorderSum= 0, rightBorderSum = 0;
for (int j= center+1; j <= right; j++)
{
rightBorderSum+= a[j];
if (rightBorderSum> maxRightBorderSum)
maxRightBorderSum= rightBorderSum;
}
return max3(maxLeftSum,maxRightSum,
maxLeftBorderSum+ maxRightBorderSum);
}
long maxSubSum3(const vector<int>&a)
{
return maxSumRec(a,0, a.size()-1);
}
另外max3(long,long,long)表示求三個long中的最大值：
//求出三個long中的最大值
long max3(long a, long b, long c)
{
if (a< b)
{
a= b;
}
if (a> c)
return a;
else
return c;
}
對這個算法進行分析：
T(1) = 1
T(N) = 2T(N/2) +O(N)
最後得出算法的復雜度為：O(NlogN) 。
算法四：
下面介紹一個線性的算法，這個算法是許多聰明算法的典型：運行時間是明顯的，但是正確性則很不明顯（不容易理解）。
//線性的算法O(N)
[cpp]
<SPAN style="FONT-SIZE: 14px">long maxSubSum4(const vector<int>&a)
{
long maxSum= 0, thisSum = 0;
for (int j= 0; j < a.size(); j++)
{
thisSum+= a[j];
if (thisSum> maxSum)
maxSum= thisSum;
else if (thisSum< 0)
thisSum= 0;
}
return maxSum;
}</SPAN>
long maxSubSum4(const vector<int>&a)
{
long maxSum= 0, thisSum = 0;
for (int j= 0; j < a.size(); j++)
{
thisSum+= a[j];
if (thisSum> maxSum)
maxSum= thisSum;
else if (thisSum< 0)
thisSum= 0;
}
return maxSum;
}
很容易理解時間界O(N) 是正確的，但是要是弄明白為什麼正確就比較費力了。其實這個是算法二的一個改進。分析的時候也是i代表當前序列的起點，j代表當前序列的終點。如果我們不需要知道最佳子序列的位置，那麼i就可以優化掉。
重點的一個思想是：如果a[i]是負數那麼它不可能代表最有序列的起點，因為任何包含a[i]的作為起點的子序列都可以通過用a[i+1]作為起點來改進。類似的有，任何的負的子序列不可能是最優子序列的前綴。例如說，循環中我們檢測到從a[i]到a[j]的子序列是負數，那麼我們就可以推進i。關鍵的結論是我們不僅可以把i推進到i+1，而且我們實際可以把它一直推進到j+1。
舉例來說，令p是i+1到j之間的任何一個下標，由於前面假設了a[i]+…+a[j]是負數，則開始於下標p的任意子序列都不會大於在下標i並且包含從a[i]到a[p-1]的子序列對應的子序列（j是使得從下標i開始成為負數的第一個下標）。因此，把i推進到j+1是安全的，不會錯過最優解。注意的是：雖然，如果有以a[j]結尾的某序列和是負數就表明了這個序列中的任何一個數不可能是與a[j]後面的數形成的最大子序列的開頭，但是並不表明a[j]前面的某個序列就不是最大序列，也就是說不能確定最大子序列在a[j]前還是a[j]後，即最大子序列位置不能求出。但是能確保maxSum的值是當前最大的子序列和。這個算法還有一個有點就是，它只對數據進行一次掃描，一旦a[j]被讀入處理就不需要再記憶。它是一個聯機算法。聯機算法：在任意時刻算法都能夠對它已讀入的數據給出當前數據的解。
