首页 > 代码库 > 蓝桥杯中的最大子段和问题

蓝桥杯中的最大子段和问题

2024-08-03 11:33:52   219人阅读

题目内容：
给定长度为n的整数序列，a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大.或者求出最大的这个和.例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4].
输入描述
第一行为一个整数n，表示数组有n个数据，第二行依次输入n个整数

 输出描述
计算出n个整数中连续k个数的最大和


 输入样例
5
1 2 3 4 5
7
6 -5 5 8 -13 5 7


输出样例
15

14

分析：若记b[j]为由a中有元素1到元素j（1 <= j <= n）中的最大子段和，那么对于每个j的取值都会有一个子段的最大子段和，那么对于整个数组的最大子段和的求解就是找出这些小子段里面最大子段和中的最大的那个。之后由b的定义可知，如果b[j - 1] > 0,则b[j] = b[j - 1] + a[j],否则b[j] = a[ji],由此就可以得出求出最大子段和的递推公式

int MaxSum(int n,int a[])
{
	int i;
	int sum = 0,b = 0;
	for(i = 1;i <= n; i++)
	{
		if(b > 0)
			b = b + a[i];
		else
			b = a[i];
		if(b > sum)
			sum = b;
	}
	return sum;
}
代码其实很简单，是吧~~~！！！

蓝桥杯中的最大子段和问题


联系
我们