最大子列和的四种算法
题目描述：
给定n个整数序列{A1,A2,...,An}，求函数 f(i,j)=max{ 0,sum(ai,a(i+1),...,aj)}的最大值。
算法一：暴力破解法
算出所有的子列和，找出最大的，即为所求。
代码如下：
int maxSubseqSum1(int a[]) {
int preSum = -1, maxSum = -1; //presentSum记录当前Sum,MaxSum记录最大子列和。
int left = -1, right = -1; //left、right记录最大子列的左右端点值。
for (int i = 0; i < n; i++) { //i记录左端点
for (int j = i; j < n; j++) { //j记录右端点
preSum = 0;
for (int k = i; k <= j; k++) {
preSum += a[k]; //累加计算a[i]->a[j]的子列和
}
if (preSum > maxSum) {
maxSum = preSum; //更新最大值及其对应的左右边界
left = i;
right = j;
}
}
}
printf("in maxSubseqSum1() left=%d,right=%d,maxSum=%d\t暴力破解法\n", left, right, maxSum);
return maxSum;
} 时间复杂度较容易由3层嵌套for循环得出为
可改进的主要点在于，如已知当前从i到j的子列和时，再计算i到j+1的子列和时，i到j的子列和又重新算一遍，显然是冗余的，是完全没有必要的，只需加一个j+1元素即可。
那么可以改进之后可以得出算法2。
算法二：暴力破解法改进版
同样为，算出所有的子列和，找出最大的，即为所求。但在具体是线上进行改进。
代码如下：
int maxSubseqSum2(int a[]) {
int preSum = -1, maxSum = -1; //presentSum记录当前Sum,MaxSum记录最大子列和。
int left = -1, right = -1; //left、right记录最大子列的左右端点值。
for (int i = 0; i < n; i++) { //i记录左端点
preSum = 0;
for (int j = i; j < n; j++) { //j记录右端点
preSum += a[j]; //对于相同的i不同的j，只需在j-1层循环的基础上加一项a[j]即可。
if (preSum > maxSum) {
maxSum = preSum; //更新最大值及其对应的左右边界
left = i;
right = j;
}
}
}
printf("in maxSubseqSum2() left=%d,right=%d,maxSum=%d\t暴力破解改进版算法\n", left, right, maxSum);
return maxSum;
} 改进版在对于相同的i不同的j的子列和计算时，在j-1层循环的基础上加一项a[j]的即可得出i到j的子列和。
不难看出该算法的时间复杂度为T(n)=O(n^2)。较法一已经有较大提升。
但是，当n到达10000、100000 、1000000时仍为一个较恐怖的的时间复杂度，因此借用分而治之的思想提出更好的算法三。
算法三：分而治之（分治法）
分治法是基于多项分支递归的一种很重要的算法。“分而治之”就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即为子问题的解的合并。诸如快速排序、归并排序、傅里叶变换、快速傅里叶变换等算法都极大程度上采用了分治法的基本思想。
分治法通常以数学归纳法来验证。而其复杂度多数情况下是以解递推关系式来判定。
运用到最大子列和问题中就可简述为：先“分”，即将数列分为两半，最大子列必只有左半边、右半边、或者两者中间这三种情况，依次求出三种情况的解；再“治”，求三个最大子列和的最大解即可得到整个数列的最大子列和。
依据上述思想可得出该题的分治算法简要的四步：
- 将数列从中间分为两个等长或者数量差值为1的两个子数列。
- 递归使用该算法分别求出左半边的最大子列和和右半边的最大子列和。
- 计算跨越中线的最大子列和，即从中线开始向左右两边分别遍历，得出跨越中线的最大子列和。
- 求三者的最大值即可。
其代码具体描述如下：
//分治法递归求最大子列和
int divCon(int list[], int left, int right) {
int maxLeftSum, maxRightSum; //记录左右两边数列的最大子列和
int maxLBorderSum = 0, maxRBorderSum = 0; //记录跨越中线的最大子列和
if (left == right) { //当left=right时，表示当前递归到只有一个数字的子列
if (list[left] > 0) {
return list[left]; //若该值>0则表示可以使最大子列和增加，故返回改值。
} else
return 0; //若改值<=0则表示不能增大最大子列和返回0。
}
//“分”
int center = (left + right) / 2; //计算中间点
maxLeftSum = divCon(list, left, center); //递归解决左半边最大子列和
maxRightSum = divCon(list, center + 1, right); //递归解决左半边最大子列和
//求跨越边界的最大子列和。
int leftBorderSum = 0, rightBorderSum = 0; //记录向左、向右的边界上当前扫描的和
//求中线以左的最大值
for (int i = center; i >= left; i--) {
leftBorderSum += list[i];
if (leftBorderSum > maxLBorderSum) //如果当前扫描的左半边的和大于左半边整体的和则更新最大值
maxLBorderSum = leftBorderSum;
}
//求中线以右的最大值
for (int i = center + 1; i < right; i++) {
rightBorderSum += list[i];
if (rightBorderSum > maxRBorderSum) //如果当前扫描的左半边的和大于左半边整体的和则更新最大值
maxRBorderSum = rightBorderSum;
}
//“治” 求左数列、右数列、跨越边界的数列，三个子问题的最大解。
return maxOfThNum(maxLeftSum, maxRightSum, maxLBorderSum + maxRBorderSum);
}
//求三个数的最大值函数
int maxOfThNum(int a, int b, int c) {
return a > b ? a > c ? a : c : b > c ? b : c;
}
int maxSubseqSum3(int list[]) {
int maxSum = divCon(list, 0, n - 1);
printf("in maxSubseqSum3() maxSum=%d\t分而治之算法\n", maxSum);
return maxSum;
} 分治法主要分为三个部分进行求解，因此时间复杂度的计算也应该分为三部分，其中在“分”的过程中每一半都为$T(n/2)$，故左右两部分的时间复杂度为$2T(n/2)$；对于跨越中线的子列和是通过两个for循环分别求解中线以左、以右的两部分的子列和，因此最差时间复杂度为遍历整个数组，故而时间复杂度为$T(n)$。
综上所述，对于时间复杂度可得如下递推式：
通过对数列的数次分割，直至被分为1个数组元素时满足$n/2^k=1$，即为$2^k=n$，因此可以得到时间复杂度为：
对比于暴力破解法，时间复杂已经有一个不错的提升，比如当n的数量级来到$10^4$时，已经有较为优异的表现。
但是，在该算法的第6~11行及21~31行我们不难发现这样子一个规律：当某子列为正数时可以增大最大子列和，若为负数则不可能使得最大子列和增加。
因此进一步分析可以得出方法四：在线处理算法。
算法四：在线处理算法
通过“在线的”思想，即无须获取全部数组元素就可以进行先行处理，可以对输入的每一个数据进行立即处理，使得算法的结果是对于当前已经读入的数据都成立的解。也就是说当某个地方的输入发生中断时，程序可以返回当前已经输入的数据的正确当前解。因此在线思想是完全区别于上述所提的三种算法的。
在线处理算法的核心思想为：
如果整数序列{a1,a2,...,an}的最大子列和是{ai,a(i+1),...,aj}，那么必有（ai+a(i+1)+...+al>=0）对任意的i<=l<=j成立。因此，当某当前子列为负时，则应考察新的以i+1为左边界的子列进行计算。
其代码具体描述如下：
int maxSubseqSum4(int list[]) {
int preSum = 0, maxSum = 0; //preSum记录当前子列和，maxSum记录最大子列和
int left = -1, right = -1; //标记最大子列的左右边界
for (int i = 0; i < n; i++) {
preSum += list[i]; //累加下一个元素
if (preSum > maxSum) { //若累加后当前子列和大于最大子列和则更新
maxSum = preSum;
right = i; //修改右边界指针
} else if (preSum < 0) { //若累加使得当前子列和变为负数，则应当丢弃该子列。
preSum = 0; //因为其不可能使最大子列和增大。
left = i+1; //修改左边界指针
}
}
printf("in maxSubseqSum4() left=%d,right=%d,maxSum=%d\t在线处理算法\n", left, right, maxSum);
return maxSum;
} 对于该算法的时间复杂度由算法代码较易得出为T(n)=O(n)，但是优秀的算法，因其思想与普通算法思想有较大的差异，所以导致算法的正确性表现的不是很直观，需要通过实际例子深入理解。
by...Ss1Two...2023/01/03
