动态规划算法--蛮力算法求最大子段和
发布时间：2020-12-13 21:10:59 所属栏目：PHP教程 来源：网络整理
导读：问题： 给定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[4],a[5],a[6]
|
问题： 给定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[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[] = { ⑵,⑵};
sum = MaxSum(buf,NR(buf)) ;
printf("%dn",sum);
return 0 ;
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |