最大子序列和問題

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

問題描述

給定一個整數數組，求出這組數字子序列和的最大值（為簡單起見，若數組中所有數字都為負數，則返回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(N³)的算法，算法本身很容易理解，而且很直觀的感覺做了很多無用操作。例如：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(N²)。在日常工作中，做到這步我就滿足了，幾乎不會去想是否還有（時間上）更優的方法。

算法三


 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(N²) < O(2ⁿ) < O(N!) ，這有點數學常識的一眼就能比較出來。

參考資料：

最大子序列和問題

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

posted @ 2014-08-14 10:36 萊布尼茨閱讀(1598) 評論(0) 收藏舉報

刷新頁面返回頂部

萊布尼茨

此處不歸牛頓管

最大子序列和問題

公告