动态规划——最大字段和

【问题描述】

给定由n个整数组成的序列a1,a2,…,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。
依此定义， 例如， 当(a1,a2, a3, a4, a5,a6)=(-2, 11, -4, 13, -5, -2)时，最大子段和为20。

【问题分析】

【代码实现】

#include<stdio.h>
int main()
{
	int get_max(int n, int a[]);
	int n;//输入数组的个数
	int a[1000];//记录所输入的数组
	int i,max;
	printf("输入数组的长度：");
	scanf("%d",&n);
	printf("请输入数组元素：\n");
	for (i = 0; i<n; i++)
	{
		scanf("%d",&a[i]);
	}
	max = get_max(n, a);
	printf("该数组序列最大字段和为：\n");
	printf("%d\n", max);
	return 0;
}
int get_max(int n, int a[])
{
	int c[1000];
	int i;
	int max = 0;
	c[0] = a[0];
	//核心算法求最大子树和并记录在max中
	for (i = 1; i<n; i++)
	{
		if (c[i-1]>0)
			c[i] = c[i - 1] + a[i];
		else
			c[i] = a[i];
		if (c[i]>max)
			max = c[i];
	}
	return max;
}

【运行结果】

运行结果仅供参考