問題描述：輸入是一個大小為n的整型數組，要求輸出數組的任何連續子數組中的最大值。例如：輸入的數組為array[10] = {31,-41,59,26,-53,58,97,-93,-23,84};輸出最大連續子數組和為array[2...6]：187

　　算法1:對所有滿足0<=i<=j<=n的(i,j)整數對進行迭代，對每個整數對，程序都要計算array[i...j]的總和，并檢驗該總和是否大于迄今為止的最大總和。

算法1的偽代碼描述如下：

1 maxsofar = 0 2 for(i=0;i<n;++j) 3 for(j=i;j<n;++j) 4 tmepsum = 0 5 for(k=i;k<=j;++k) 6 tempsum += array[k] 7 maxsofar = max(maxsofar,tempmax)

這段代碼簡潔明了，便于理解，但是程序執行的速度很慢，時間復雜度為O(n^3)。

　　算法2:對于算法1有一個明顯的方法可以使其運行起來快得多。使得時間復雜度控制住平方O(n^2)。

第一個平方算法注意到，array[i...j]的總和與前面計算出的總和（array[i...j-1]）密切相關，利用這一點可以達到算法2。

算法2_1的偽代碼描述如下：

1 maxsofar = 0 2 for(i=0;i<n;++i) 3 tempsum = 0; 4 for(j=i;j<n;++j) 5 tempsum += array[j] 6 maxsofar = max(maxsofar,tempsum)

第二個平方算法是引入一個數組curarray，大小也為n，通過空間來換取時間，通過訪問外循環執行之前計算[0...i]各個連續字段總和。curarrary中的第i個元素包含array[0...i]中各個數的累加和，所以x[i...j]中各個數的總和可以通過計算curarray[j] -curarray[i-1]得到.

算法2_2的偽代碼描述如下：

1 curarray[-1] = 0 2 for(i=0;i<n;++i) 3 curarray[i] = curarray[i-1]+x[i] 4 maxsofar = 0 5 for(i=0;i<n;++i) 6 for(j=i;j<n;++j) 7 sum = curarray[j]-curarray[i-1] 8 maxsofar = max(maxsofar,sum)

　　算法3：可以考慮采用法治算法。初始問題是要處理大小為n的數組，所以可以將其劃分為兩個子數組a和b，然后遞歸的找出a、b中元素總和最大的子數組分別為MaxA、MaxB。而最大子數組要么在a中，要么在b中，要么跨越a和b之間的邊界，我們將跨越邊界的最大子數組記為MaxC。我們通過分治算法計算處了MaxA和MaxB，通過某種辦法計算處MaxC。然后返回三個中的最大值就是我們所要的最大子數組和。算法的時間復雜度為O(nlogn)。如何計算MaxC呢？通過觀察發現，MaxC在a中的部分是a中包含右邊界的最大子數組，而MaxC在b中的部分是b中包含左邊界的最大子數組。將這些綜合一起我們得到算法3：

1 int maxsum3(1,n) 2 { 3 if(n<1) //空數組 4 return 0 5 if(n==1) 6 //只有一個元素的數組 7 return array[1] 8 mid = n/2 //分為兩部分 9 lmax = tempsum =0 10 //包含右邊界的最大子數組和 11 for(i=mid;i>=1;--i) 12 sum + array[i] 13 lmax = max(lmax,sum) 14 rmax = sum =0;//包含左邊界的最大子數組和 15 for(i=mid;i<n;++i) 16 sum += array[i] 17 rmax = max(rmax,sum) 18 return max(lmax+rmax,maxsum3(1,mid),maxsum3(mid+1,n)) 19 }

　　算法4：我們現在采用操作數組的最簡單的算法：從數組最左端(元素x[0])開始掃描，一直到最右端(元素array[n-1])為止，并記下所遇到的最大總和的子數組。最大總和開始設為0.假設我們已經解決了array[0...i-1]的問題，那么如何將其擴展為包含x[i]的問題呢？我們用類似于分治算法的原理：前i個元素中，最大總和子數組要么在前i-1個元素中（將其存maxsofar中），要么其結束位置為i（將其存入maxendinghere中）。不從頭開始計算結束位置為i的最大子數組，而是利用結束位置為i-1的最大子數組進行計算。這樣就得到了算法4：

1 maxsofar = 0 2 maxendinghere = 0 3 for(i=0;i<n;++i) 4 maxendinghere = max(maxendinghere+array[i],0) 5 maxsofar = max(maxsofar,maxendinghere)

　　理解這個程序的關鍵在于maxendinghere。在循環中第一個賦值語句之前，maxendinghere是結束位置為i-1的最大子數組的和，賦值語句將其修改為結束位置為i的最大子數組的和。若加上array[i]的后的結果為正值，則該賦值語句使maxendinghere增大x[i]，若加上x[i]之后結果為負值，該賦值語句將maxendinghere重新設置為0（因為結束位置為i的最大子數組現在為空）。這個地方有些難度，需要認真思考揣摩。時間復雜度為O(n),線性算法，效率最高。

下面針對這4個算法寫一個完成的程序來進行測試，程序如下：

1 。#include <iostream> 2 using namespace std; //求兩個數種最大值 3 int max(const int m,const int n) 4 { 5 return m>n ? m : n; 6 } //求三個整數中的最大值 7 int max(const int x,const int y,const int z) 8 { 9 int temp = x>y ? x : y; 10 temp = temp > z ? temp : z; 11 return temp; 12 } //算法1函數實現 13 int maxsum1(int *array,const size_t len) 14 { 15 int maxsofar = 0; 16 int tempsum = 0; 17 for(size_t i=0;i<len;++i) 18 for(size_t j=i;j<len;++j) 19 { 20 tempsum = 0; 21 for(size_t k =i;k<=j;++k) 22 { 23 tempsum += array[k]; 24 maxsofar = max(maxsofar,tempsum); 25 } 26 } 27 return maxsofar; 28 } //算法2.1的實現 29 int maxsum2_1(int *array,const size_t len) 30 { 31 int maxsofar = 0; 32 int tempsum = 0; 33 for(size_t i=0;i<len;++i) 34 { 35 tempsum = 0; 36 for(size_t j=i;j<len;++j) 37 { 38 tempsum += array[j]; 39 maxsofar = max(maxsofar,tempsum); 40 } 41 } 42 return maxsofar; 43 } //算法2.2的實現 44 int maxsum2_2(int *array,const size_t len) 45 { 46 int *curarray =NULL; 47 int maxsofar = 0; 48 if(len>0) 49 curarray = new int[len]; 50 curarray[-1] = 0; 51 for(size_t i=0;i<len;++i) 52 curarray[i] = curarray[i-1] + array[i]; 53 for(size_t j=0;j<len;++j) 54 for(size_t k=j;k<len;++k) 55 //tempsum = curarray[k] - curarray[j-1]; 56 maxsofar = max(maxsofar,curarray[k]-curarray[j-1]); 57 return maxsofar; 58 } //算法3的實現 59 int maxsum3(int *array,const int begin,const int end) 60 { 61 int mid = 0; 62 int lmax=0,rmax =0; 63 int tempsum = 0; 64 if(begin==end) 65 return array[begin]; 66 mid = (begin+end) / 2; 67 for(int i=mid;i>=begin;--i) 68 { 69 tempsum += array[i]; 70 lmax = max(lmax,tempsum); 71 } 72 tempsum = 0; 73 for(int j=mid+1;j<=end;++j) 74 { 75 tempsum += array[j]; 76 rmax = max(rmax,tempsum); 77 } 78 return max(lmax+rmax,maxsum3(array,begin,mid),maxsum3(array,mid+1,end)); 79 } //算法4的實現 80 int maxsum4(int *array,const size_t len) 81 { 82 int maxendinghere = 0; 83 int maxsofar = 0; 84 for(size_t i=0;i<len;++i) 85 { 86 maxendinghere = max(maxendinghere+array[i],0); 87 maxsofar = max(maxsofar,maxendinghere); 88 } 89 return maxsofar; 90 } int main() 91 { 92 int array[10] = {31,-41,59,26,-53,58,97,-93,-23,84}; 93 int choise; 94 cout<<"1.算法1"<<endl; 95 cout<<"2.算法2_1"<<endl; 96 cout<<"1.算法1"<<endl; 97 cout<<"3.算法3"<<endl; 98 cout<<"4.算法4"<<endl; 99 cout<<"5.算法2_2" <<endl; 100 cout<<"0.退出"<<endl; 101 while(1) 102 { 103 cout<<"選擇算法："; 104 cin>>choise; 105 cout<<"數組的最大字段和為："; 106 switch(choise) 107 { 108 case 1: 109 cout<<maxsum1(array,10)<<endl; 110 break; 111 case 2: 112 cout<<maxsum2_1(array,10)<<endl; 113 break; 114 case 3: 115 cout<<maxsum3(array,0,9)<<endl; 116 break; 117 case 4: 118 cout<<maxsum4(array,10)<<endl; 119 break; 120 case 5: 121 cout<<maxsum2_2(array,10)<<endl; 122 break; 123 case 0: 124 exit(0); 125 } 126 } 127 return 0; 128 }

參考文獻：《編程珠璣》第二版 第八章 算法設計的藝術

總結

以上是生活随笔為你收集整理的数组的连续最大子段和的全部內容，希望文章能夠幫你解決所遇到的問題。

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