求最大子序列和及其位置（四种经典方法）

算法部分

#include <iostream>
#include <vector>
using namespace std;
//http://blog.163.com/kevinlee_2010/blog/static/169820820201010495438247/
//http://www.cnblogs.com/mingzi/archive/2008/07/22/1248793.html
//http://www.richardma.org/blog/?p=167207
//http://blog.csdn.net/smallacmer/article/details/7188234

//s(tart)表示最大子序列的开始位置，e(nd)表示结束位置
//这里如果有多于一个的最大子序列的时候，只记录开始位置最低的那个
int s=0;
int e=0;

//穷举法，复杂度O(n^3)
long maxSubSum1(const vector<int> &a){
	long maxSum=0;
	for (int i=0; i<a.size();i++)
	{
		for (int j=i;j<a.size();j++)
		{
			long thisSum=0;
			for (int k=i; k<=j; k++)
			{
				thisSum+=a[k];
			}
			if (thisSum>maxSum){
				maxSum=thisSum;
				s=i;
				e=j;
			}
		}
	}
	return maxSum;
}

//也是穷举法，不过减去了上面的一些不必要操作O(n^2)  
long maxSubSum2(const vector<int> &a){
	long maxSum=0;
	for (int i=0; i<a.size(); i++)
	{
		long thisSum=0;
		for (int j=i; j<a.size(); j++)
		{
			thisSum+=a[j];
			if (thisSum>maxSum){
				maxSum=thisSum;
				s=i;
				e=j;
			}
		}
	}
	return maxSum;
}

long max3(long a, long b, long c){
	if(a<b)
		a=b;
	if(a>c)
		return a;
	else
		return c;
}

long maxSumRec(const vector<int> a, int left, int right){
	if(left == right)
	{
		//其实这个基准值在后面计算的时候可以保证
		//在这里不必多此一举
		if(a[left]>0)
			return a[left];
		else
			return 0;
	}

	int center=(left+right)/2;
	long maxLeftSum=maxSumRec(a,left,center);
	long maxRightSum=maxSumRec(a,center+1,right);

	//某段序列中，求含最右侧元素序列和的最大值
	long maxLeftBorderSum=0,leftBorderSum=0;
	for (int i=center; i>=left; i--)
	{
		leftBorderSum+=a[i];
		if(leftBorderSum>maxLeftBorderSum)
		{
			maxLeftBorderSum=leftBorderSum;
			s=i;
		}
	}
	//某段序列中，求含最左侧元素序列和的最大值
	long maxRightBorderSum=0,rightBorderSum=0;
	for (int j=center+1; j<=right; j++)
	{
		rightBorderSum+=a[j];
		if(rightBorderSum>maxRightBorderSum)
		{
			maxRightBorderSum=rightBorderSum;
			e=j;
		}
	}

	return max3(maxLeftSum,maxRightSum,
		maxLeftBorderSum+maxRightBorderSum);
}

//该方法我们采用“分治策略”（divide-and-conquer）,相对复杂的O(NlogN)的解法
//最大子序列可能在三个地方出现，或者在左半部，或者在右半部，
//或者跨越输入数据的中部而占据左右两部分。前两种情况递归求解，
//第三种情况的最大和可以通过求出前半部分最大和（包含前半部分最后一个元素）
//以及后半部分最大和（包含后半部分的第一个元素）相加而得到。
long maxSubSum3(const vector<int> &a){
	return maxSumRec(a,0,a.size()-1);
}

//如果a[i]是负数那么它不可能代表最有序列的起点，因为任何包含a[i]的作为起点的子
//序列都可以通过用a[i+1]作为起点来改进。类似的有，任何的负的子序列不可能是最优
//子序列的前缀。例如说，循环中我们检测到从a[i]到a[j]的子序列是负数，那么我们就可以推进i。
//关键的结论是我们不仅可以把i推进到i+1，而且我们实际可以把它一直推进到j+1。
long maxSubSum4(const vector<int> &a){
	long maxSum=0;
	long thisSum=0;
	int t=0;
	for (int j=0; j<a.size(); j++)
	{
		thisSum+=a[j];
		if(thisSum>maxSum){
			maxSum=thisSum;
			s=t;
			e=j;
		}
		else if(thisSum<0){
			thisSum=0;
			t=j+1;
		}
	}
	return maxSum;
}

 

测试程序

int main()
{
	cout << "==================input========================" << endl << endl;
	vector<int> input;
	input.push_back(-2);
	input.push_back(11);
	input.push_back(-4);
	input.push_back(13);
	input.push_back(-5);
	input.push_back(-2);

	cout << "------------------maxSubSum1--------------------" << endl;
	cout << maxSubSum2(input) << endl;
	cout << "start:" << s << endl;
	cout << "end:" << e << endl;

	cout << "------------------maxSubSum2--------------------" << endl;
	cout << maxSubSum1(input) << endl;
	cout << "start:" << s << endl;
	cout << "end:" << e << endl;

	cout << "------------------maxSubSum3--------------------" << endl;
	cout << maxSubSum3(input) << endl;
	cout << "start:" << s << endl;
	cout << "end:" << e << endl;

	cout << "------------------maxSubSum4--------------------" << endl;
	cout << maxSubSum4(input) << endl;
	cout << "start:" << s << endl;
	cout << "end:" << e << endl;

	cout << "==================input2========================" << endl << endl;
	vector<int> input2;
	input2.push_back(-6);
	input2.push_back(2);
	input2.push_back(4);
	input2.push_back(-7);
	input2.push_back(5);
	input2.push_back(3);
	input2.push_back(2);
	input2.push_back(-1);
	input2.push_back(6);
	input2.push_back(-9);
	input2.push_back(10);
	input2.push_back(-2);
	cout << "------------------maxSubSum1--------------------" << endl;
	cout << maxSubSum2(input2) << endl;
	cout << "start:" << s << endl;
	cout << "end:" << e << endl;

	cout << "------------------maxSubSum2--------------------" << endl;
	cout << maxSubSum1(input2) << endl;
	cout << "start:" << s << endl;
	cout << "end:" << e << endl;

	cout << "------------------maxSubSum3--------------------" << endl;
	cout << maxSubSum3(input2) << endl;
	cout << "start:" << s << endl;
	cout << "end:" << e << endl;

	cout << "------------------maxSubSum4--------------------" << endl;
	cout << maxSubSum4(input2) << endl;
	cout << "start:" << s << endl;
	cout << "end:" << e << endl;

	return 0;
}