动态规划算法--蛮力算法求最大子段和

问题： 给定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 ;
}