首页 > 编程语言 > 详细

【原题】求两个不相交的连续子数组的最大和

时间:2015-08-31 01:13:50      阅读:883      评论:0      收藏:0      [点我收藏+]

题目:

         有一个整数数组n,a和b是n里两个互不相交的子数组。返回sum(a)+sum(b)的最大值。

分析:

新建两个数组left和right,left[i]表示n[0:i]的连续子数组的最大和,right[i]表示n[i:length-1]的连续子数组的最大和。left[i]+right[i+1]的最大值就是答案。

int SumOfTwoSubarray(const vector<int> &n)
{
	if (n.size() < 2)
	{
		throw exception();
	}
	vector<int> left(n.size()), right(n.size());
	int sum = n[0], maxnum = n[0];
	left[0] = n[0];
	right.back() = n.back();
	for (uint32_t i = 1; i < n.size()-1; ++i)
	{
		if (sum > 0)
			sum += n[i];
		else
			sum = n[i];
		if (sum > maxnum)
		{
			maxnum = sum;			
		}	
		left[i] = maxnum;
	}
	sum = n.back();
	maxnum = n.back();
	for (uint32_t i = n.size()-2; i >=1; --i)
	{
		if (sum > 0)
			sum += n[i];
		else
			sum = n[i];
		if (sum > maxnum)
		{
			maxnum = sum;
		}
		right[i] = maxnum;
	}
	int res = 0x80000000;
	for (uint32_t i = 0; i < n.size() - 1; ++i)
		res = max(res, left[i] + right[i + 1]);
	return res;
}




版权声明:本文为博主原创文章,未经博主允许不得转载。

【原题】求两个不相交的连续子数组的最大和

原文:http://blog.csdn.net/bupt8846/article/details/48115931

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