求输入序列的最大子序列

序列的最大子序列"/>

求输入序列的最大子序列

问题：给出一个有限长度的实数序列，求出其子序列中和为最大的子序列值？

方法1：设置两个循环遍历序列，分别作为子序列的左右两端，再加一个循环将子序列中所有项相加，最后算法的时间复杂度为。

void maxSubList(int list[],int length) {int maxSublist = 0,l=0,r=0;int thisSubList = 0;int i ,j,k;for (i = 0; i < length; i++) {		//定义序列左端for (j = i; j < length; j++) {	//定义序列右端for (k = i; k < j; k++) {thisSubList += list[j];		//将序列从左端i加到右端j}if (thisSubList > maxSublist){maxSublist = thisSubList;		//更新最大序列l = i;							//记录最大子序列的左右下标r = j;}}}cout << maxSublist << endl;cout << l<<","<<r << endl;
}

方法2：首先思考，算法需要做的是遍历所有的子序列，在遍历过程中就可以将所有的子序列进行求和比较，然后更新最大子序列即可，所以第三个循环可以省去。最后算法的时间复杂度为。

void maxSubList(int list[],int length) {int maxSublist = 0,l=0,r=0;int thisSubList = 0;int i ,j;for (i = 0; i < length; i++) {		//定义序列左端thisSubList = 0;for (j = i; j < length; j++) {	//定义序列右端thisSubList += list[j];		//将序列从左端i加到右端jif (thisSubList > maxSublist){maxSublist = thisSubList;		//更新最大序列l = i;							//记录最大子序列的左右下标r = j;}}}cout << maxSublist << endl;cout << l<<","<<r << endl;
}

方法3：根据分治的思想，对序列进行划分。最大子序列可以在左边子式，可以在右边子式，也可以是跨越中间的子式，然后将左右子式依次划分，求子式中的最大子式。如图所示：

int MaxSubList(int numL, int numR,int* list) {if (numL == numR) {return list[numL];				//定义最终的返回值}int l = 0, r = 0;int numMid = (numL+numR)/2;int lMax = MaxSubList(numL, numMid, list);//回调求左边的最大子式int rMax = MaxSubList(numMid + 1, numR, list);//回调求右边的最大子式int midMax=0,sumL=list[numMid],sumR=list[numMid+1],sum=0;  for (int i = numMid; i >=numL; i--) {sum += list[i];									if (sum > sumL)										//计算中间部分的最大子式sumL = sum;}								sum = 0;for (int j = numMid + 1; j <= numR; j++) {sum += list[j];if (sum > sumR)sumR = sum;}midMax = sumL + sumR;if (lMax > midMax){midMax = lMax;								//判断最后的大小}if (rMax > midMax){midMax = rMax;}return  midMax; 
}

最后算法的时间复杂度为。

4、最后介绍一下在线处理算法。在线处理的意思就是边读入数据边进行判断整理，在逐项累加的过程中判断累加数列是否为负，若为负数，则加后面的项只会使后面的数变小，所以清空累加数列。然后判断累加后的数列与之前记录的最大数列之间的大小，最后得出结果。它的算法复杂度为。

int MaxSubList(int* list,int length) {int thisSum = 0, maxSum = 0,startNum=0,stopNum=0;for (int i = 0; i < length; i++) {thisSum += list[i];					//逐项累加if (thisSum < 0) {thisSum = 0;					//判断累加后的数列若为负数，则舍弃该累加数列startNum = i + 1;				//同时将子数列起始序号重置}if (thisSum > maxSum) {maxSum = thisSum;				//判断累加后的数列若大于之前记录的最大子数列，则对最大子数列进行更新stopNum = i;					//同时将子数列的终止序号重置}}cout << startNum << "," << stopNum << endl;return maxSum;

该算法不仅时间复杂度最低，而且还能同时求出最大子数列的起始，是目前最优的算法。