問(wèn)題描述： 給定一個(gè)整數(shù)數(shù)組，找到一個(gè)具有最大和的子數(shù)組，返回其最大和。
樣例： 給出數(shù)組[?2,2,?3,4,?1,2,1,?5,3]，符合要求的子數(shù)組為[4,?1,2,1]，其最大和為6
分析： 解決這個(gè)問(wèn)題至少有4種方法
算法1 窮舉法
我們窮舉出所有的子數(shù)組，然后從這些子數(shù)組中找出最大的
int MaxSubseqSum1(int List[], int N){ int ThisSum, MaxSum = 0; int i,j,k; for (i = 0; i < N; i++)//i是子數(shù)組的左端 { for (j = i; j < N; j++)//j是子數(shù)組的右端 { ThisSum = 0;//ThisSum是List[i]到List[j]的子數(shù)組的和 for (k = i; k <= j; k++) ThisSum += List[k]; if(ThisSum > MaxSum)//如果剛得到的這個(gè)子數(shù)組和更大 MaxSum = ThisSum;//則更新結(jié)果 } } return MaxSum;}時(shí)間復(fù)雜度：O(N3)
算法2 優(yōu)化的窮舉法
第一個(gè)算法中，最里面的循環(huán)，對(duì)于固定的i，當(dāng)j增大了1，k循環(huán)需要從新從i加到j。事實(shí)上，第j部就加上List[j]即可。
int MaxSubseqSum2(int List[], int N){ int ThisSum, MaxSum = 0; int i,j; for (i = 0; i < N; i++) { ThisSum = 0; for (j = i; j < N; j++) { ThisSum += List[j]; // 對(duì)于相同的i，不同的j，只要在j-1次循環(huán)的基礎(chǔ)上累加1項(xiàng)即可 if(ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum;}時(shí)間復(fù)雜度：O(N2)
算法3：分而治之
步驟： 1. 將序列分為左右兩個(gè)子數(shù)組 2. 遞歸地求兩個(gè)子數(shù)組的最大和S左和S右 3. 從中間的點(diǎn)分別找出左右，跨過(guò)分界線的最大子數(shù)組的和S中 4. Smax=maxS左,S右,S中
/*算法3：分而治之*/inx Max3(int A, int B, int C){ return A > B ? A > C ? A : C : B > C ? B : C;}int DivideAndConquer(int List[], int left, int right){ int MaxLeftSum, MaxRightSum; int MaxLeftBorderSum, MaxRightBorderSum; int LeftBorderSum, RightBorderSum; int center,i; if(left == right) //遞歸終止條件，子數(shù)組只有一個(gè)數(shù)字 if(List[left] > 0) return List[left]; else return 0; //分的過(guò)程 center = (left+right)/2; MaxLeftSum = DivideAndConquer(List,left,center) MaxRightSum = DivideAndConquer(List,center+1,right) //跨界求最大子數(shù)組和 MaxLeftBorderSum = 0; LeftBorderSum = 0; for (i = center; i >= left; i--) { LeftBorderSum += List[i]; if(LeftBorderSum > MaxLeftBorderSum) MaxLeftBorderSum = LeftBorderSum; }//左邊掃描結(jié)束 MaxRightBorderSum = 0; RightBorderSum = 0; for (i = center+1; i < right; i++) { RightBorderSum += List[]; if(RightBorderSum > MaxRightBorderSum) MaxRightBorderSum = RightBorderSum; }//右邊掃描結(jié)束 //治的過(guò)程 return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);}int MaxSubseqSum3(int List[], int N){ return DivideAndConquer(List, 0, N-1);}算法4：在線處理（動(dòng)態(tài)規(guī)劃）
核心思想：一旦發(fā)現(xiàn)子數(shù)組的和為負(fù)數(shù)，棄置，重新一個(gè)新數(shù)組。
int MaxSubseqSum4(int List[], int N){ int ThisSum, MaxSum; int int; ThisSum = MaxSum = 0; for (i = 0; i < N; i++) { ThisSum += List[i]; if(ThisSum > MaxSum) MaxSum = ThisSum; else if(ThisSum < 0) ThisSum = 0; } return MaxSum;}python
#動(dòng)態(tài)規(guī)劃def MaxSubseqSum(A): max_ending_here = max_so_far = A[0] for x in A[1:]: max_ending_here = max(x, max_ending_here + x) max_so_far = max(max_so_far, max_ending_here) return max_so_far
