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

算法部分

#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