最大连续子数组和

浏览数：25 / 时间：2015年06月08日

最大连续子数组和

1. 题目描述

输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值，要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

2. 解法一：三层搜索

这个解法使用了3层搜索，时间复杂度为O(n^3)。

第一层搜索：i遍历数组中所有数，作为子数组的起始点；

第二层搜索：j遍历i到数组最后一个数，作为子数组的终止点；

第三层搜索：k遍历i到j，求得当前子数组和curSum，与maxSum比较；

我们再用下图来展示上层搜索过程：

#include<iostream>
using namespace std; 

int MaxSubSum(int *a, int num)
{
	int curSum=0; 
	int maxSum=a[0]; 
	for(int i=0; i<num; i++)
	{
		for(int j=i; j<num; j++)
		{
			for(int k=i; k<=j; k++)
			{
				curSum+=a[k]; 
			}
			if(curSum>maxSum)
				maxSum=curSum; 

			curSum=0; 
		}
	}
	return maxSum; 
}

int main()
{
	int a[8]={1, -2, 3, 10, -4, 7, 2, -5}; 
	int num=8; 
	int maxSum=MaxSubSum(a, num); 

	cout<<maxSum<<endl; 

	return 0; 
}

3. 解法二：前顾后盼法

其实我们是需要遍历一次即可，在遍历的这一次中，我们可以同时完成curSum和maxSum的工作。思路如下：

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.04.md

对第j+1个元素有两种选择：要么放入前面找到的子数组，要么做为新子数组的第一个元素；
如果currSum加上当前元素a[j]后不小于a[j]，则令currSum加上a[j]，否则currSum重新赋值，置为下一个元素，即currSum = a[j]。
同时，当currSum > maxSum，则更新maxSum = currSum，否则保持原值，不更新。

代码如下：

#include<iostream>
using namespace std; 

int MaxSubSum(int *a, int num)
{
	int curSum=0; 
	int maxSum=a[0]; 
	for(int i=0; i<num; i++)
	{
		curSum=(curSum+a[i]>a[i]) ? curSum+a[i] : a[i]; 
		maxSum=maxSum>curSum ? maxSum : curSum; 
	}
	return maxSum; 
}

int main()
{
	int a[8]={1, -2, 3, 10, -4, 7, 2, -5}; 
	int num=8; 
	int maxSum=MaxSubSum(a, num); 

	cout<<maxSum<<endl; 

	return 0; 
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

最大连续子数组和