程序媛決定先學(xué)學(xué)數(shù)據(jù)結(jié)構(gòu)，從算法復(fù)雜度入門啦~

問題描述很簡單，對于給定的整數(shù)A1，A2,.......An(可能有負數(shù))，求Ak+A2+........+Aj的最大值（k=<j=<n），ji就是找出這一串數(shù)的和最大非空連續(xù)子數(shù)組。(為了方便起見，如果所有的整數(shù)均為負數(shù)，則最大的子序列和為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++)		{			//用來存儲當前序列的求和結(jié)果			int thisSum = 0;			//將子序列的值依次加入求和結(jié)果			for (int k = i; k <= j; k++)			{				thisSum += a[k];			}			//存儲兩者的最大值			if(thisSum > maxSum)				maxSum = thisSum;		}	}	return maxSum;}
這種算法的時間復(fù)雜度為O(N3).（立方）
算法2：窮舉優(yōu)化，可以省去第三重循環(huán)，算法復(fù)雜度為O(N2)。（平方）
//計算并返回所最大子序列的和：窮舉優(yōu)化int maxSubSum2(const vector<int> & a){	//用來存儲最大子序列的和	int maxSum = 0;	//i標記子序列的左邊界	for (int i = 0; i < a.size(); i++)	{		//用來存儲當前子序列的求和結(jié)果		int thisSum = 0;		//j標記子序列的右邊界		for (int j = i; j < a.size(); j++)		{			//將子序列的值加入上次求和結(jié)果			thisSum += a[j];			//存儲兩者的最大值			if(thisSum > maxSum)				maxSum = thisSum;		}	}	return maxSum;} 算法3：分而治之
分而治之，顧名思義分為兩個部分分：把大問題分成大致相等的兩個子問題，然后遞歸的進行求解。治：把兩個子問題的解合并到一起并再做少量的附加工作。在最大子序列和的問題里，最大子序列的和可能出現(xiàn)在三個地方：整個出現(xiàn)在輸入數(shù)據(jù)的左半部整個輸入數(shù)據(jù)的右半部橫跨左右兩個部分對于前兩種可以遞歸求解，對于第三種，可以把左右兩個部分的和分別求出，然后加在一起。
算法復(fù)雜度為O(NlogN)。
/計算并返回所最大子序列的和：分而治之int maxSubSum3(const vector<int> & a,int left,int right){	//基礎(chǔ)情況：單個元素。直接返回這個數(shù)值或者0	if(left == right)	{		return a[left];	}	//獲取中點	int center = (left + right) / 2;	/* 整個出現(xiàn)在輸入數(shù)據(jù)的左半部的最大子序列求和 */	int leftMaxSum = maxSubSum3(a,left,center);	/* 整個出現(xiàn)在輸入數(shù)據(jù)的右半部的最大子序列求和 */	int rightMaxSum = maxSubSum3(a,center+1,right);	//計算左右兩個子序列求和結(jié)果的最大值	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);	}	//返回求和和前面算出結(jié)果的最大值	return max( lrMaxSum, maxLeftSum+maxRightSum);} 算法4,：及時處理
//計算并返回所最大子序列的和：最優(yōu)算法int maxSubSum4(const vector<int> & a){	//最終結(jié)果	int maxSum = 0;	//當前求和	int nowSum = 0;	//遍歷序列的所有元素	for (int j = 0; j < a.size(); j++)	{		//將當前元素添加到結(jié)果中		nowSum += a[j];		//如果大于最大值，則存儲為新的最大值		if(nowSum > maxSum)			maxSum = nowSum;		else if(nowSum < 0)			nowSum = 0;	}	return maxSum;}算法復(fù)雜度為O(N)。原文鏈接：點擊打開鏈接