问题： 给定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]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。
最大子段和是动态规划中的一种。
当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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define NR(x) sizeof(x)/sizeof(x[0])
int MaxSum(int a[] , int n)
{
int sum = 0 ;
int b = 0 ;
int i ;
for(i = 1 ; i < n ; i++)
{
if(b > 0)
b = b + a[i] ;
else
b = a[i] ;
if(b > sum)
sum = b ;
}
return sum ;
}
int main(void)
{
int sum ;
int buf[] = { -2, 11, -4, 13, -5, -2};
sum = MaxSum(buf,NR(buf)) ;
printf("%d\n",sum);
return 0 ;
}
