最大子序列和问题从O（N^3）到线性的算法

       算法复杂度，从开始学习算法分析之后就一直在讨论着这个问题，很多人都认为，计算机相关人才只是“高级蓝领”，“技术民工”，那为什么计算机的大牛们依然乐此不疲呢？我想，是因为他们发现了思考的乐趣。

       有时候，稍加思考，你所做的事情就会变得格外的美妙，有时候，更简短的代码带来的却是更高的执行效率，生活，恰是需要这样的点睛之笔。

       好了，前奏铺垫的有点长，下面进入正题，通过对大家所熟知的一道题的分析，最大子序列和的问题，让我们来初步感受一下编程的美丽：

       题目是这样描述的，给定指定的整数序列（可能是负数）A1，A2…..An,寻找（并标识）使得Ai至Aj的连续的和值最大的子序列。

       首先初步分析一下，假设输入的是1,3,-5,6,-3这五个数，那么最大的明显是1，3，-5,6所组成的子序列，包含四项，数组下标从0开始，到3为止。而对于一个全为负数的序列，最长公共子序列的和值应该是0，理由在于，由0个整数所组成的空子序列也是一个子序列。

       问题分析到这里，大家应该对问题有了初步了解了，那么对于一道寻值的问题，我们一般第一反应所想到的恐怕就是“暴力求解”了，将每一个可能的子序列都找出来，然后一一比对，比如一个长度为6的序列，他的子序列的长度就有0到6这7种大情况，再把每一种情况细分(如长度为3的子序列，数组的下标索引可以是0,1,2,3),把所有的情况都列出来，这样毫无疑问是可以找到答案的，通过这样的分析，我们的O(N^3)的算法就出炉了，如下：

      

/**
* O(N^3)算法
* @return 最大公共子序列的和
*/
public int maxSubsequenceSum1(int a[]){
	int maxSum=0;
	for(int i=0;i<a.length;i++){
		for(int j=i;j<a.length;j++){
			int thisSum=0;
			for(int k=i;k<=j;k++){
				thisSum+=a[k];
				if(thisSum>maxSum){
					maxSum=thisSum;
					seqStart=i;//最大公共子序列索引的起始坐标
					seqEnd=j;//最大公共子序列索引的末尾坐标
				}
			}
		}
	}
	System.out.println(seqStart);
	System.out.println(seqEnd);
	return maxSum;
}

       不难看出，这个算法的运行时间完全由最内层的for循环决定，而里层执行的次数正好等于满足1<=i<=k<=j<=N的有序三元组（i,j,k）的个数，大家可以自己用数学公式证明一下，这个有序三元组的个数是N(N+1)(N+2)/6。这种“暴力求解”的优点是，编码非常简单，理解起来也很容易，算法越简单就越容易正确地编程实现。不过这样的方法很明显效率偏低，三层嵌套因此导致算法的复杂度是立方级的，不过我们要注意的是，三个连续的循环表现出的是线性行为，也就是说，不是简单的N*N*N的算法。那么我们是不是可以去掉一个循环来提高程序的执行效率呢？请看以下分析：

       很明显，上面的算法有很多不必要的计算，假设我们已经计算出了i,…,j-1的和，那么计算子序列i,…j的和是不是很简单呢？只需要再进行一次计算。立方算法恰恰就丢掉了这一个信息，如下的改进算法，使用的是两个而不是三个循环嵌套：

 

/**
 * O(N^2)算法
 */
public int maxSubsequenceSum2(int a[]){
	int maxSum=0;
	for(int i=0;i<a.length;i++){
		int thisSum=0;
		for(int j=i;j<a.length;j++){
			thisSum+=a[j];
			if(thisSum>maxSum){
				maxSum=thisSum;
				seqStart=i;
				seqEnd=j;
			}
		}
	}
	System.out.println(seqStart);
	System.out.println(seqEnd);
	return maxSum;
} 

       很多人可能做到上面一步就停止了，我们已经完成了从N^3到N^2的飞跃，那么是不是还可以删除一个循环来达到线性算法呢？想法是美妙的，但是具体实施起来却没有那么简单。假设Ai,j是满足Si,j<0的第一个子序列，如下图（图画的不好，请见谅）：

      

       容易证明，在假设的情况下，如果q>j,那么Ai,q不是最大连续子序列，因为序列的索引完全可以从下一个大于0的数开始。所以当我们得到了第一个小于0的子序列之后，完全可以从这个序列里面跳出来，继续计算接下来的序列段，避免重复的计算，那么这一次的算法就需要大家仔细的思考一下了，下面给出一种方法：

       

/**
 * 线性算法
 */
public int maxSubsequenceSum3(int a[]){
	int maxSum=0;
	int thisSum=0;
	for(int i=0,j=0;j<a.length;j++){
		thisSum+=a[j];
		if(thisSum>maxSum){
			maxSum=thisSum;
			seqStart=i;
			seqEnd=j;
		}
		else if(thisSum<0){
			thisSum=0;
			i=j+1;
		}
	}
	System.out.println(seqStart);
	System.out.println(seqEnd);
	return maxSum;
}

 

       虽然这种算法通过跳过不可能的条件而达到了更高的效率，不过，相比“暴力求解”来说，正确性就没那么明显了，相反，其中的很多条件都需要我们证明，我们已经通过一个简单的数学运算证明了它的正确性。数学将我们带入了编程的世界，又为我们提供了坚实的基础。编程其实很多时候不是方法的照搬，通过思考，我们能够得到更优的方法，就像我们热爱探索世界的眼睛。

       走进编程的世界，感受编程之美吧。