最大子序列和問題

最大子序列和問題乃經典算法問題之一，很多教科書和技術文章都對此有詳述，部落客重新整理一遍乃是為了消化和日後翻閱，不喜勿噴。

問題描述

給定一個整數數組，求出這組數字子序列和的最大值（為簡單起見，若數組中所有數字都為負數，則傳回0）。例如：

序列：-2 11 -4 13 -5 -2，則最大子序列和為20。

序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，則最大子序列和為16。

算法一

1 //窮舉法，所有的組合都加一遍，得到最大值
 2 int GetMaxSubsequenceSum1(int[] array)
 3 {
 4     int tempSum = 0, maxSum = 0, i, j, k;
 5     for (i = 0; i < array.Length; i++)
 6     {
 7         for (j = i; j < array.Length; j++)
 8         {
 9             tempSum = 0;
10             for (k = i; k < j; k++)//當j++後，已得到的原j個數字的和又要重新計算擷取——在算法2中避免了這步重複計算的問題
11                 tempSum += array[k];
12             if (tempSum > maxSum)
13                 maxSum = tempSum;
14         }
15     }
16     return maxSum;
17 }      

這是一個O(N3)的算法，算法本身很容易了解，而且很直覺的感覺做了很多無用操作。例如：i = 0, j = 3時，會計算a[0] + a[1] +…+ a[3]；而當i = 0, j = 4時候又會計算a[0] + a[1] +…a[4]。算法二會對此做一改進。（有句“格言”：計算任何事情不要超過一次。）

算法二

1 int GetMaxSubsequenceSum2(int[] array)
 2 {
 3     int tempSum = 0, maxSum = 0, i, j;
 4     for (i = 0; i < array.Length; i++)
 5     {
 6         tempSum = 0;
 7         for (j = i; j < array.Length; j++)
 8         {
 9             tempSum += array[j];//tempSum存儲前j個數的和
10             if (tempSum > maxSum)
11                 maxSum = tempSum;
12         }
13     }
14     return maxSum;
15 }      

比算法一少了一層for循環，so，複雜度也降為O(N2)。在日常工作中，做到這步我就滿足了，幾乎不會去想是否還有（時間上）更優的方法。

算法三

1 //分治政策（divide-and-conquer）
 2 int GetMaxSubsequenceSum3(int[] array, int left, int right)
 3 {
 4     if (left == right)//此時可判定隻有一個元素
 5         return array[left] < 0 ? 0 : array[left];//若是負數則傳回0
 6 
 7     int center = (left + right) / 2;
 8     int maxLeftSum = GetMaxSubsequenceSum3(array, left, center);
 9     int maxRightSum = GetMaxSubsequenceSum3(array, center + 1, right);
10 
11     //求出以左邊對後一個數字結尾的序列最大值 
12     int maxLeftBorderSum = 0, leftBorderSum = 0;
13     for (int i = center; i >= left; i--)
14     {
15         leftBorderSum += array[i];
16         if (leftBorderSum > maxLeftBorderSum)
17             maxLeftBorderSum = leftBorderSum;
18     }
19 
20     //求出以右邊對後一個數字結尾的序列最大值 
21     int maxRightBorderSum = 0, rightBorderSum = 0;
22     for (int j = center + 1; j <= right; j++)
23     {
24         rightBorderSum += array[j];
25         if (rightBorderSum > maxRightBorderSum)
26             maxRightBorderSum = rightBorderSum;
27     }
28 
29     return Math.Max(Math.Max(maxLeftSum, maxRightSum), maxLeftBorderSum + maxRightBorderSum);
30 }      

所謂分治政策，将大的問題分成大緻相等的若幹子問題，對它們求解并合并為最終解，依靠的即是遞歸算法。具體到上述算法，複雜度為O(NlogN)（猜測NlogN中的系數N乃是第8、9行兩次遞歸運算帶出來的）。分析算法最讓人困惑的大概就是對數的出現。除分治算法外，可将對數常出現的規律概括為以下一般法則：如果一個算法用常數時間（O(1)）将問題的大小削減為其一部分（通常是二分之一），那麼該算法的複雜度就是O(logN)。另一方面，如果使用常數時間隻是把問題減少一個常數（如将問題減少1），那麼這種算法就是O(N)的。那麼，是否還有更優的（時間上）算法呢？

算法四

1 int GetMaxSubsequenceSum4(int[] array)
 2 {
 3     int tempSum = 0, maxSum = 0;
 4     for (int j = 0; j < array.Length; j++)
 5     {
 6         tempSum += array[j];
 7         if (tempSum > maxSum)
 8             maxSum = tempSum;
 9         else if (tempSum < 0)
10             tempSum = 0;
11     }
12     return maxSum; 
13 }      

很容易了解上述代碼的時間複雜度是O(N)，但是要是弄明白為什麼正确就比較費力了。其實這個是算法二的一個改進。分析的時候也是i代表目前序列的起點，j代表目前序列的終點。如果我們不需要知道最佳子序列的位置，那麼i就可以優化掉。

重點的一個思想是：如果a[i]是負數那麼它不可能代表最有序列的起點，因為任何包含a[i]的作為起點的子序列都可以通過用a[i+1]作為起點來改進。類似的有，任何的負的子序列不可能是最優子序列的字首。例如說，循環中我們檢測到從a[i]到a[j]的子序列是負數，那麼我們就可以推進i。關鍵的結論是我們不僅可以把i推進到i+1，而且我們實際可以把它一直推進到j+1（j是使得從下标i開始成為負數的第一個下标）。舉例來說，令p是i+1到j之間的任何一個下标，由于前面假設了a[i]+…+a[j]是負數，則開始于下标p的任意子序列都不會大于在下标i并且包含從a[i]到a[p-1]的子序列對應的子序列。是以，把i推進到j+1是安全的，不會錯過最優解。注意的是：雖然，如果有以a[j]結尾的某序列和是負數就表明了這個序列中的任何一個數不可能是與a[j]後面的數形成的最大子序列的開頭，但是并不表明a[j]前面的某個序列就不是最大序列，也就是說不能确定最大子序列在a[j]前還是a[j]後，即最大子序列位置不能求出。但是能確定maxSum的值是目前最大的子序列和。這個算法還有一個有點就是，它隻對資料進行一次掃描，一旦a[j]被讀入處理就不需要再記憶。它是一個聯機算法。

聯機算法：在任意時刻算法都能夠對它已讀入的資料給出目前資料的解。

常量空間線性時間的聯機算法幾乎是完美的算法。

其它

關于算法三中提到的對數複雜度，除分治算法外，還有對分查找（已排序集合）、歐幾裡得算法（查找最大公約數）、幂運算等，都有該特點。

時間複雜度比較（由小到大）：O(1) < O(logN) < O(N) < O(NlogN) < O(N2) < O(2n) < O(N!) ，這有點數學常識的一眼就能比較出來。

參考資料：

最大子序列和問題

資料結構與算法分析——C語言描述第二版（美 Mark Allen Weiss著  馮舜玺 譯）第2章