問題： 給定n個整數（可能為負數）組成的序列a[1],a[2],a[3],…,a[n],求該序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。當所給的整數均為負數時定義子段和為0，依此定義，所求的最優值為： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，當（a[1],a[2],a[3],a[4],a[5],a[6]）=(-20,11,-4,13,-5,-2)時，最大子段和為20。
最大子段和是動態規劃中的一種。
分治法,遞推法,
分治法
算法描述如下
針對最大子段和這個具體問題本身的結構，我們還可以從算法設計的策略上對上述O(n^2)計算時間算法進行更進一步的改進。從問題的解結構也可以看出，它適合於用分治法求解。
如果將所給的序列a[1:n]分為長度相等的兩段a[1:n/2]和a[n/2+1:n],分別求出這兩段的最大子段和，則a[1:n]的最大子段和有三種情況：
（1） a[1:n]的最大子段和與a[1:n/2]的最大子段和相同
（2） a[1:n]的最大子段和與a[n/2+1:n]的最大子段和相同
（3） a[1:n]的最大子段和為a[i]+…+a[j]，並且1<=i<=n/2，n/2+1<=j<=n。
對於（1）和（2）兩種情況可遞歸求得，但是對於情況（3），容易看出a[n/2]，a[n/2+1]在最大子段中。因此，我們可以在a[1:n/2]中計算出s1=max(a[n/2]+a[n/2-1]+…+a[i]),0<=i<=n/2，並在a[n/2+1:n]中計算出s2= max(a[n/2+1]+a[n/2+2]+…+a[i])，n/2+1<=i<=n。則s1+s2為出現情況（3）的最大子段和。據此可以設計出最大子段和問題的分治算法如下：
#include<stdio.h>#define MAX 100int maxsub(int left,int right);int a[MAX];int main(){ int i,count; scanf("%d",&count); for(i=0;i<count;i++) scanf("%d",&a[i]); printf("%d\n",maxsub(0,count-1)); return 0;}int maxsub(int left,int right){ int center,i,sum,left_sum,right_sum,left_max,right_max; center=(left+right)>>1; if(left==right) return a[left]>0?a[left]:0; else { left_sum=maxsub(left,center); right_sum=maxsub(center+1,right); sum=0; left_max=0; for(i=center;i>=left;i--) { sum+=a[i]; if(sum>left_max) left_max=sum; } sum=0; right_max=0; for(i=center+1;i<=right;i++) { sum+=a[i]; if(sum>right_max) right_max=sum; } sum=right_max+left_max; if(sum<left_sum) sum=left_sum; if(sum<right_sum) sum=right_sum; } return sum;}遞推法
在對於上述分治算法的分析中我們注意到，若記b[j]=max(a[i]+a[i+1]+..+a[j]),其中1<=i<=j,並且i<=j<=n。則所求的最大子段和為max b[j]，1<=j<=n。
由b[j]的定義可易知，當b[j-1]>0時b[j]=b[j-1]+a[j]，否則b[j]=a[j]。故b[j]的遞推方程為:
b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。
代碼如下：
#include <stdlib.h>#include<stdio.h>int main(){ int count; int a[100]; int b[100]; int i; int max; scanf("%d",&count); for(i=0; i<count; i++) { scanf("%d",&a[i]); } b[0]=a[0]; max=b[0]; for(i=1; i<count; i++) { if(b[i-1]>0) b[i]=b[i-1]+a[i]; else b[i]=a[i]; if(b[i]>max) max=b[i]; } printf("%d\n",max); return 0;}