首页 > 编程语言 > 详细

连续字数组的最大和

时间:2015-05-27 21:08:32      阅读:162      评论:0      收藏:0      [点我收藏+]

 题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间杂度为O(n)。

此题思路比较简单,直接上代码,注意考虑无效的输入。

//全局变量,判断输入参数是否无效
bool g_InputInvalid=false;

int FindGreatestSumOfArray(int *data, int length)
{
	if (data==NULL||length<=0)
	{
		g_InputInvalid=true;
		return 0;
	}
	g_InputInvalid=false;

	//当前子数组和
	int CurSum=0;
	//记录连续子数组的最大和,初始值设置为很小的负数
	int GreatestSum = 0x80000000;
	for (int i=0; i<length; ++i)
	{
		if (CurSum<0)
			CurSum=data[i];//从第i个数重新开始累加
		else 
			CurSum+=data[i];
		if (CurSum>GreatestSum)
			GreatestSum=CurSum;
	}
	return GreatestSum;
}


连续字数组的最大和

原文:http://blog.csdn.net/lsh_2013/article/details/46051561

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!