问题
给定整数: ，
求 的最大值（为方便起见，如果所有的整数均为负数，则最大子序列和为0）

例如
对于输入：-2,11,-4,13,-5,-2，答案为20，即从到
分析
这个问题之所以有意思，是因为存在很多求解它的算法。

解法一：穷举遍历
老老实实的穷举出所有的可能，代码如下：

//计算并返回所最大子序列的和：穷举遍历
int maxSubSum1(const vector<int> & a)
{
	//用来存储最大子序列的和
	int maxSum = 0;

	//i标记子序列的头
	for (int i = 0; i < a.size(); i++)
	{
		//j标记子序列的尾
		for (int j = i; j < a.size(); j++)
		{
			//用来存储当前头尾计算的求和结果
			int thisSum = 0;

			//将子序列的值依次加入求和结果
			for (int k = i; k <= j; k++)
			{
				thisSum += a[k];
			}

			//存储两者的最大值
			if(thisSum > maxSum)
				maxSum = thisSum;
		}
	}

	return maxSum;
}


这是大多数人都会想到的方法：把所有的可能都列举出来，然后再把子序列的所有值都加起来求和。
简单粗暴的解决了问题，而且还很好理解。

解法二：枚举优化
其实第三个for循环完全没有必要，在第二层for循环的时候就计算求得的和并且继续带入下一轮的for循环即可：

//计算并返回所最大子序列的和：穷举优化
int maxSubSum2(const vector<int> & a)
{
	//用来存储最大子序列的和
	int maxSum = 0;

	//i标记子序列的头
	for (int i = 0; i < a.size(); i++)
	{
		//用来存储当前头尾计算的求和结果
		int thisSum = 0;

		//j标记子序列的尾
		for (int j = i; j < a.size(); j++)
		{

			//将子序列的值加入上次求和结果
			thisSum += a[j];

			//存储两者的最大值
			if(thisSum > maxSum)
				maxSum = thisSum;
		}
	}

	return maxSum;
}

解法三：分而治之
分而治之，顾名思义分为两个部分

分：把大问题分成大致相等的两个子问题，然后递归的进行求解。
治：把两个子问题的解合并到一起并再做少量的附加工作。
在最大子序列和的问题里，最大子序列的和可能出现在三个地方：

整个出现在输入数据的左半部
整个输入数据的右半部
横跨左右两个部分
对于前两种可以递归求解，对于第三种，可以把左右两个部分的和分别求出，然后加在一起。
具体的代码如下：

//计算并返回所最大子序列的和：分而治之
int maxSubSum3(const vector<int> & a,int left,int right)
{
	//基础情况：单个元素。直接返回这个数值或者0
	if(left == right)
	{
		return a[left];
	}

	//获取中点
	int center = (left + right) / 2;

	/* 整个出现在输入数据的左半部的最大子序列求和 */
	int leftMaxSum = maxSubSum3(a,left,center);

	/* 整个出现在输入数据的右半部的最大子序列求和 */
	int rightMaxSum = maxSubSum3(a,center+1,right);

	//计算左右两个子序列求和结果的最大值
	int lrMaxSum = max(leftMaxSum,rightMaxSum);


	/* 横跨左右两个部分的最大子序列求和 */

	//从center向左处理左半边
	int maxLeftSum = 0;
	int leftSum = 0;
	for (int i = center; i >= left; i--)
	{
		leftSum += a[i];
		maxLeftSum = max(maxLeftSum,leftSum);
	}

	//从center向右处理右半边
	int maxRightSum = 0;
	int rightSum = 0;
	for (int j = center+1; j <= right; j++)
	{
		rightSum += a[j];
		maxRightSum = max(maxRightSum,rightSum);
	}

	//返回求和和前面算出结果的最大值
	return max( lrMaxSum, maxLeftSum+maxRightSum);
}

解法四：联机算法
先来解释一下联机算法的概念：

联机算法：在任意时刻，算法对要操作的数据只读入（扫描）一次，一旦被读入并处理，它就不需要在被记忆了。而在此处理过程中算法能对它已经读入的数据立即给出相应子序列问题的正确答案。具有这种特性的算法叫做联机算法（on-line algorithm）。

对于这个问题，代码如下：

//计算并返回所最大子序列的和：最优算法
int maxSubSum4(const vector<int> & a)
{
	//最终结果
	int maxSum = 0;
	//当前求和
	int nowSum = 0;

	//遍历序列的所有元素
	for (int j = 0; j < a.size(); j++)
	{
		//将当前元素添加到结果中
		nowSum += a[j];

		//如果大于最大值，则存储为新的最大值
		if(nowSum > maxSum)
			maxSum = nowSum;
		else if(nowSum < 0)
			nowSum = 0;
	}

	return maxSum;
}

另附联机算法+记录路径的题：https://blog.csdn.net/nuoyanli/article/details/86232061