算法探討——再議經典算法問題：求最大子序列和、絕對值最大子序列和以及其區間

給定任一數字序列，如{-5,4,-20,16,-2,-3}，求出其最大子序列和，絕對值最大子序列和以及對應的區間，在這個例子中，人肉計算可知最大子序列和為16，區間為[3,3)（數組下標從0開始），而絕對值最大子序列和為-21，區間為[0,2]，那么算法如何描述及實現呢？

在經典的書籍《數據結構與算法分析 C語言描述第2版》中，作者向我們介紹了求最大子序列和的三種算法，時間復雜度從O(N³)下降到O(N)，求最大子序列和絕對值和以及其區間是我對這一問題的擴展。

一、求最大子序列和以及其區間

求最大子序列和的算法相對簡單，并且可以使用動態規劃思想將其優化至O(N)，問題的關鍵：前面已輸入的元素的計算結果并不依賴于后面的輸入。

O(N²)算法：N次遍歷數組，對其中每一個元素，繼續遍歷后續每個元素，并求和，如發現比當前和大，替換當前和。

C/C++實現：

1 int maxsub(const int a[],int n) 2 { 3 int sum, max, i, j, begin, end; 4 begin = end = max = 0; 5 for(i = 0;i < n;i++) 6 { 7 sum = 0; 8 for(j = i;j<n;j++) 9 { 10 sum += a[j]; 11 printf("the second level loop %d loop sum = %d\n",j,sum); 12 printf("the second level loop %d loop max = %d\n",j,max); 13 if(sum > max) 14 { 15 max = sum; 16 begin = i; 17 end = j; 18 } 19 } 20 printf("the %d loop max = %d\n",i+1,max); 21 } 22 printf("--final-- Begin = %d, End = %d\n",begin,end); 23 return max; 24 }

循環結束后，begin與end的值即對應的區間。
O(N)算法：動態規劃思想，也稱on-line algorithm，即，對于每一個輸入，不依賴于后面輸入，對每一個輸入，立即計算其結果，并保存，然后與后續輸入進行比較，若和變大，產生更新。若和總是變小，丟棄之前的輸入。

C/C++實現：

int maxsublinear(const int a[], int n) {int i;int curSum = 0; /* 當前序列和 */int maxSum = 0; /* 最大序列和 */int begin = end = 0;/* 開始循環求子序列和 */for (i = 0; i < n; i++){curSum = curSum + a[i];/* 與最大子序列和比較，更新最大子序列和 */if (curSum > maxSum){maxSum = curSum;end = i;}/* 動態規劃部分，舍棄當前和為負的子序列 */if (curSum < 0){curSum = 0;begin = i + 1 >= n ? i : i + 1;}}return maxSum; }

二、求絕對值最大子序列和以及對應的區間

這個問題是對第一個問題的擴展，但比第一個問題復雜的多，O(N²)算法基本相同，也容易理解。

O(N2) C/C++實現：

1 int maxabssub(const int a[],int n) 2 { 3 int sum, max, i, j, begin, end; 4 begin = end = max = 0; 5 for(i = 0;i < n;i++) 6 { 7 sum = 0; 8 for(j = i;j<n;j++) 9 { 10 sum += a[j]; 11 printf("the second level loop %d loop sum = %d\n",j,sum); 12 printf("the second level loop %d loop max = %d\n",j,max); 13 if(abs(sum) > max) 14 { 15 max = abs(sum); 16 begin = i; 17 end = j; 18 } 19 } 20 printf("the %d loop max = %d\n",i+1,max); 21 } 22 printf("--final-- Begin = %d, End = %d\n",begin,end); 23 return max; 24 }

O(N)算法，在竹風撫荷塘同學的幫助下，順利求解。思路其實很簡單，絕對值最大的子序列和，要么是和最大，要么是和最小，類似問題一中O(N)算法，同時求每一個輸入可能得到的最大和或最小和，再比較即可。下面是C/C++代碼實現：

?

1 int maxAbsSubLinear(int a[], int n) 2 { 3 int posiSum, negaSum, curSum, max, j, begin, end, posiBegin, posiEnd, negaBegin, negaEnd, flag; 4 posiSum = negaSum = curSum = max = j = begin = end = posiBegin = posiEnd = negaBegin = negaEnd = flag = 0; 5 6 for(j = 0;j < n;j++) 7 { 8 if(posiSum + a[j] > a[j]) 9 { 10 posiSum += a[j]; 11 } 12 else 13 { 14 posiSum = a[j]; 15 posiBegin = j; 16 } 17 if(negaSum + a[j] < a[j]) 18 { 19 negaSum += a[j]; 20 } 21 else 22 { 23 negaSum = a[j]; 24 negaBegin = j; 25 } 26 27 if( abs(posiSum) > abs(negaSum) ) 28 { 29 curSum = abs(posiSum); 30 posiEnd = j; 31 flag = 1; 32 } 33 else 34 { 35 curSum = abs(negaSum); 36 negaEnd = j; 37 flag = 0; 38 } 39 40 if(curSum > max) 41 { 42 max = curSum; 43 if(flag) 44 { 45 begin = posiBegin; 46 end = posiEnd; 47 } 48 else 49 { 50 begin = negaBegin; 51 end = negaEnd; 52 } 53 } 54 55 printf("IN ABS LINEAR -- LOOP %d, posiSum = %d, negaSum = %d, curSum = %d, max=%d, begin = %d, end = %d\n", j+1, posiSum, negaSum, curSum, max, begin, end); 56 } 57 58 printf("--LINEAR final-- Begin = %d, End = %d\n",begin,end); 59 return max; 60 }

?

再次感謝竹風撫荷塘同學。

轉載于:https://www.cnblogs.com/ccdev/archive/2012/09/09/2677328.html

總結

以上是生活随笔為你收集整理的算法探讨——再议经典算法问题：求最大子序列和、绝对值最大子序列和以及其区间...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。