程序媛决定先学学数据结构，从算法复杂度入门啦~

问题描述很简单，对于给定的整数A1，A2,.......An(可能有负数)，求Ak+A2+........+Aj的最大值（k=<j=<n），ji就是找出这一串数的和最大非空连续子数组。(为了方便起见，如果所有的整数均为负数，则最大的子序列和为0)。

      算法1：穷举算法：

//计算并返回所最大子序列的和：穷举遍历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;}
这种算法的时间复杂度为O(N3).（立方）
算法2：穷举优化，可以省去第三重循环，算法复杂度为O(N2)。（平方）
//计算并返回所最大子序列的和：穷举优化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;} 算法3：分而治之
分而治之，顾名思义分为两个部分分：把大问题分成大致相等的两个子问题，然后递归的进行求解。治：把两个子问题的解合并到一起并再做少量的附加工作。在最大子序列和的问题里，最大子序列的和可能出现在三个地方：整个出现在输入数据的左半部整个输入数据的右半部横跨左右两个部分对于前两种可以递归求解，对于第三种，可以把左右两个部分的和分别求出，然后加在一起。
算法复杂度为O(NlogN)。
/计算并返回所最大子序列的和：分而治之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);} 算法4,：及时处理
//计算并返回所最大子序列的和：最优算法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;}算法复杂度为O(N)。原文链接：点击打开链接