算法进化历程之“最大连续子序列之和”
算法进化历程之“最大连续子序列之和”巧若拙（欢迎转载，但请注明出处：http://blog.）
题目描述：
给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个， 例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。
输入：
测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( < 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。
输出：
对每个测试用例，在1行里输出最大和。若所有K个元素都是负数，则定义其最大和为0。
输入示例：
6
-2 11 -4 13 -5 -2
10
-10 1 2 3 4 -5 -23 3 7 -21
6
5 -8 3 2 5 0
1
10
3
-1 -5 -2
3
-1 0 -2
0
输出示例：
20
10
10
10
0
0
算法分析：
算法1：
最直接的想法是蛮力穷举。计算每一段可能的连续子序列A[i..j]之和，然后保留最大值。由于有三层循环，故时间复杂度为O(N^3)。代码如下：
int MaxSubsequenceSum_1(const int A[], int n)//低效算法1
{
int sum, maxSum, i, j, k;
maxSum = 0;
for (i=0; i<n; i++)
{
for (j=i; j<n; j++)
{
sum = 0;
for (k=i; k<=j; k++)//计算连续子序列A[i..j]之和
{
sum += A[k];
}
if (sum > maxSum)
maxSum = sum;
}
}
return maxSum;
}
算法2：
仔细观察算法1，我们发现其实最内层循环是不必要的，因为我们可以直接在最外层循环中设置sum = 0;然后累计每一个A[j]值就可以得到A[i..j]之和了。由于只有两层循环，故时间复杂度为O(N^2)。代码如下：
int MaxSubsequenceSum_2(const int A[], int n)//低效算法2
{
int sum, maxSum, i, j, k;
maxSum = 0;
for (i=0; i<n; i++)
{
sum = 0;
for (j=i; j<n; j++)
{
sum += A[j];
if (sum > maxSum)
maxSum = sum;
}
}
return maxSum;
}
算法3：
虽然算法2把时间复杂度减小到O(N^2)，但还算不上高效的算法，我们可以采用一种“分治”策略，把序列分成左右两个部分，则最大子序列和可能在三处出现：左半部，右半部，或者跨越数据的中部而占据左右两半部分。前面两种情况可以递归求解，第三种情况需要计算出左半部最大和（必须包含左半部最右元素）以及右半部最大和（必须包含右半部最左元素），然后将这两个和加在一起。最后返回三者的最大值。
由于采用了分治算法，所以时间复杂度可以减小到O(NlogN)。
代码如下：
int MaxSubsequenceSum_3(const int A[], int n)//分治算法
{
return MaxSubSum(A, 0, n-1);
}
int MaxSubSum(const int A[], int left, int right)//分治算法子程序
{
int maxLeftSum, maxRightSum;
int maxLeftBorderSum, maxRightBorderSum;
int leftBorderSum, rightBorderSum;
int mid, i;
if (left == right)
return (A[left] > 0) ? A[left] : 0;
mid = (left + right) / 2;
maxLeftSum = MaxSubSum(A, left, mid); //递归计算左半部子序列最大和
maxRightSum = MaxSubSum(A, mid+1, right);//递归计算右半部子序列最大和
maxLeftBorderSum = leftBorderSum = 0;
for (i=mid; i>=left; i--) //从中间开始向左计算包含A[mid]子序列的最大和
{
leftBorderSum += A[i];
if (leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
maxRightBorderSum = rightBorderSum = 0;
for (i=mid+1; i<=right; i++) //从中间开始向右计算A[mid+1]子序列的最大和
{
rightBorderSum += A[i];
if (rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
return Max_3(maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum);
}
int Max_3(int a, int b, int c)
{
if (a >= b && a >= c)
return a;
if (b >= a && b >= c)
return b;
if (c >= a && c >= b)
return c;
}
算法4：
接下来要出场的是“动态规划”算法，这也是我向大家隆重推荐的算法，它的实际复杂度为O(N)，是解决此类问题的最佳算法。
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
在本题中，我们可以把前i(1<=i<=n)个元素的最大子序列和记录下来，不断增大i，最后就得到n个元素的最大子序列和。为了记录每一个子问题的解，我们设置两个数组：
int curSum[MAX];//curSum[i]用来存储A[0..i]中包含A[i]的最大连续子序列之和
int maxSum[MAX];//maxSum[i]用来存储A[0..i]中最大连续子序列之和（不一定包含A[i]）
最后maxSum[n-1];表示由n个元素构成的序列中最大连续子序列之和。
代码如下：
int MaxSubsequenceSum_4(const int A[], int n)//动态规划算法
{
int curSum[MAX];//curSum[i]用来存储包含A[i]的最大连续子序列之和
int maxSum[MAX];//maxSum[i]用来存储A[0..i]中最大连续子序列之和（不一定包含A[i]）
int i, max = 0;
maxSum[0] = curSum[0] = A[0];
for (i=1; i<n; i++)//存储各连续子序列的最大和
{
if (curSum[i-1] > 0) //若之前的连续子序列之和大于0，则把A[i]累加上去
curSum[i] = curSum[i-1] + A[i];
else //否则重新开始
curSum[i] = A[i];
maxSum[i] = (curSum[i] > maxSum[i-1]) ? curSum[i] : maxSum[i-1];
}
if (maxSum[n-1] > 0)
max = maxSum[n-1];
return max;
}
算法5：
算法4通过使用两个数组，记录每一个子问题的解。但我们注意到，本问题只需要知道maxSum[n-1]的值就行了，之前的那些元素不是必须的，而且curSum[i]的计算只依赖 curSum[i-1]，maxSum[i]的计算也只依赖maxSum[i-1]，所以没有必要把每一个curSum[i]和maxSum[i]的值都记录下来，只需记录前一个元素，然后迭代计算就可以了。
我们可以分别用变量sum和maxSum来代替数组curSum[]和maxSum[]，代码如下：
int MaxSubsequenceSum_5(const int A[], int n)//动态规划算法
{
int sum, maxSum, i;
maxSum = sum = 0;
for (i=0; i<n; i++)
{
sum += A[i];
if (sum > maxSum)
maxSum = sum;
else if (sum < 0) //连续子序列之和小于0了，则重新开始
sum = 0;
}
return maxSum;
}
如果你能顺利理解上面的算法，可以接受进一步挑战，试试下面的题目。
题目描述：
现在我认为你已经在伊格内修斯•李的“最大和”问题中获得了一个AC 。作为一个勇敢的ACMer，我们总是自我挑战更困难的问题，现在你面对的是一个更难的问题。
给定一个连续整数序列S1, S2, S3, S4... Sx, ... Sn (1 ≤ x ≤ n ≤1,000,000,-32768 ≤ Sx ≤ 32767)。我们定义一个函数sum(i, j) = Si+ ... + Sj (1 ≤ i ≤ j ≤ n).
现在给出一个整数 m (m > 0),你的任务是找到m对i和j，使得sum(i1, j1) +sum(i2, j2) + sum(i3, j3) + ... + sum(im, jm) 最大，其中 ix ≤ iy ≤ jx 或 ix ≤ jy ≤ jx 是不允许出现的。
但是我很懒，我不想写一个专门的判断模块，所以你不需要输出m对i和j，而只需输出sum(ix, jx)(1 ≤ x ≤ m)的最大值就行了。
输入：
每个测试用例将以两个整数m和n开始, 紧随其后的是n个整数S1、S2、S3……Sn。直到读入文件结束。
输出：
在一行上输出题目描述中所说的最大值。
输入示例：
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
输出示例：
6
8
算法分析：
算法6：
本题是动态规划算法的典型应用，我们可以模仿前面算法4的解法，使用一个二维数组maxSum[MAX][MAX]来存储所有将共j个元素分成i组所获得的最大连续子序列之和，其中1<=j<=n，1<=i<=m。当MAX值较大时，我们最好把二维数组maxSum[MAX][MAX]设置成全局变量，否则不能正确分配栈空间。
代码如下：
int MaxSubPlus(const int A[], int m, int n)//动态规划记录将共j个元素分成i组所获得的最大连续子序列之和
{
int maxSum[MAX][MAX] = {0};
int curSum[MAX] = {0};//curSum[i]用来存储包含A[i]的最大连续子序列之和
int i, j;
for (i=1; i<=m; i++) //动态规划，规模从小到大，用maxSum[i][j]记录将共j个元素分成i组所获得的最大连续子序列之和
{
maxSum[i][i] = curSum[i] = maxSum[i-1][i-1] + A[i];//若将i个元素分成i组，则每个元素都要用上
{
for (j=i+1; j<=n; j++)
{
if (curSum[j-1] > maxSum[i-1][j-1]) //curSum[j]存储包含A[j]的i组最大连续子序列之和
curSum[j] = curSum[j-1] + A[j];
else
curSum[j] = maxSum[i-1][j-1] + A[j];
maxSum[i][j] = (curSum[j] > maxSum[i][j-1]) ? curSum[j] : maxSum[i][j-1];
}
}
}
return maxSum[m][n];
}
算法7：
当MAX值较小时，算法6是可行的，但由于本题中的MAX=1000001，实在是太大了（实际只有把所有的数组都设为全局变量才能分配出这么大的数组空间）。所以必须模仿斐波那契数列中，不需要记录所有的F[i]值，只需迭代记录F[i-1]和F[i-2]就可以求得F[i]的方法（上题的算法5对算法4的优化也是采用了这种方法），设置以下3个数组来迭代记录中间结果：
int curSum[MAX];//用来存储包含A[j]的最大连续子序列之和
int preSum[MAX];//用来存储将共j个元素分成i-1组所获得的最大连续子序列之和
int maxSum[MAX];//用来存储将共j个元素分成i组所获得的最大连续子序列之和。
算法的基本思想是：以i和j分别作为外，内层循环变量，二者的规模都是从小到大，用maxSum[j]记录将共j个元素分成i组所获得的最大连续子序列之和。若将i个元素分成i组，则每个元素都要用上，此时maxSum[i] =curSum[i] = preSum[i-1] + A[i];
接下来不断加入新的元素，即增加j的值，计算加入新元素后能否得到更大的连续子序列和。将curSum[j-1]和 preSum[j-1]进行比较，让较大者和新元素A[j]求和，看看新的和是否会比maxSum[j-1]大，在maxSum[j]中存储目前得到的最大值。
算法的关键在于每轮计算结束都要把maxSum[]值复制到 preSum[] ，以便进行下一轮迭代计算。代码如下：
#include<stdio.h>
#include<stdlib.h>
#define MAX 1000001
int A[MAX];
int curSum[MAX];//用来存储包含A[j]的最大连续子序列之和
int preSum[MAX];//用来存储将共j个元素分成i-1组所获得的最大连续子序列之和
int maxSum[MAX];//用来存储将共j个元素分成i组所获得的最大连续子序列之和
int MaxSubPlus(const int A[], int m, int n);//动态规划记录将共j个元素分成i组所获得的最大连续子序列之和
int main(void)
{
int i, m, n;
while(scanf("%d%d",&m,&n)!=EOF)
{
for (i=1; i<=n;i++)
scanf("%d", &A[i]);
printf("%d\n", MaxSubPlus(A, m, n));
}
return 0;
}
//类似斐波那契数列，不需要记录所有的F[i]值，只需迭代记录F[i-1]和F[i-2]就可以求得F[i]
int MaxSubPlus(const int A[], int m, int n)//动态规划记录将共n个元素分成m组所获得的最大连续子序列之和
{
int i, j;
for (j=0; j<=n; j++)//初始化
preSum[j] = 0;
for (i=1; i<=m; i++) //动态规划，规模从小到大，用maxSum[j]记录将共j个元素分成i组所获得的最大连续子序列之和
{
maxSum[i] = curSum[i] = preSum[i-1] + A[i];//若将i个元素分成i组，则每个元素都要用上
for (j=i+1; j<=n; j++)
{
if (curSum[j-1] > preSum[j-1]) //curSum[j]存储包含A[j]的i组最大连续子序列之和
curSum[j] = curSum[j-1] + A[j];
else
curSum[j] = preSum[j-1] + A[j];
maxSum[j] = (curSum[j] > maxSum[j-1]) ? curSum[j] : maxSum[j-1];
}
for (j=i; j<=n; j++) //把maxSum[]值复制到 preSum[] ，进行下一轮迭代计算
preSum[j] = maxSum[j];
}
return maxSum[n];
}
到这里，最大连续子序列之和的相关算法就介绍完毕了，动态规划策略是一种高效而实用的策略，代码实现也很简单，但理解起来有一定难度，我将在接下来的系列文章中把自己对动态规划的理解记录下来，和大家分享，谢谢您的关注。
