动态规划算法--蛮力算法求最大子段和-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

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

简介: 问题: 给定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
问题: 给定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 ;
}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章