动态规划算法--蛮力算法求最大子段和
来源：程序员人生 发布时间：2016-07-08 16:40:16 阅读次数：2735次
问题： 给定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]）=(⑵,11,⑷,13,⑸,⑵)时，最大子段和为20。
最大子段和是动态计划中的1种。
当b[j⑴]>0时b[j]=b[j⑴]+a[j]，否则b[j]=a[j]。故b[j]的动态计划递归式为:
b[j]=max(b[j⑴]+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[] = { ⑵, 11, ⑷, 13, ⑸, ⑵};
sum = MaxSum(buf,NR(buf)) ;
printf("%d\n",sum);
return 0 ;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
