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

最大子序列和问题从O（N^3）到线性的算法2014-07-11 iteye cq520算法复杂度，从开始学习算法分析之后就一直在讨论着这个问题，很多人都认为，计算机相关人才只是“高级蓝领”，“技术民工”，那为什么计算机的大牛们依然乐此不疲呢？我想，是因为他们发现了思考的乐趣。

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

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

题目是这样描述的，给定指定的整数序列（可能是负数）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）的算法就出炉了，如下：

Java代码

/** * 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的和是不是很简单呢？只需要再进行一次计算。立方算法恰恰就丢掉了这一个信息，如下的改进算法，使用的是两个而不是三个循环嵌套：

Java代码

/*** 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;}