算法探讨——再议经典算法问题：求最大子序列和、绝对值最大子序列和以及其区间
给定任一数字序列，如{-5,4,-20,16,-2,-3}，求出其最大子序列和，绝对值最大子序列和以及对应的区间，在这个例子中，人肉计算可知最大子序列和为16，区间为[3,3)（数组下标从0开始），而绝对值最大子序列和为-21，区间为[0,2]，那么算法如何描述及实现呢？
在经典的书籍《数据结构与算法分析 C语言描述第2版》中，作者向我们介绍了求最大子序列和的三种算法，时间复杂度从O(N3)下降到O(N)，求最大子序列和绝对值和以及其区间是我对这一问题的扩展。
一、求最大子序列和以及其区间
求最大子序列和的算法相对简单，并且可以使用动态规划思想将其优化至O(N)，问题的关键：前面已输入的元素的计算结果并不依赖于后面的输入。
O(N2)算法：N次遍历数组，对其中每一个元素，继续遍历后续每个元素，并求和，如发现比当前和大，替换当前和。
C/C++实现：
1 int maxsub(const int a[],int n) 2 { 3int sum, max, i, j, begin, end; 4begin = end = max = 0; 5for(i = 0;i < n;i++) 6{ 7 sum = 0; 8 for(j = i;j<n;j++) 9 {10 sum += a[j];11 printf("the second level loop %d loop sum = %d\n",j,sum);12 printf("the second level loop %d loop max = %d\n",j,max);13 if(sum > max)14 {15 max = sum;16 begin = i;17 end = j;18 }19 }20 printf("the %d loop max = %d\n",i+1,max);21}22printf("--final-- Begin = %d, End = %d\n",begin,end);23return max;24 }
循环结束后，begin与end的值即对应的区间。
O(N)算法：动态规划思想，也称on-line algorithm，即，对于每一个输入，不依赖于后面输入，对每一个输入，立即计算其结果，并保存，然后与后续输入进行比较，若和变大，产生更新。若和总是变小，丢弃之前的输入。
C/C++实现：
int maxsublinear(const int a[], int n){int i;int curSum = 0; /* 当前序列和 */int maxSum = 0; /* 最大序列和 */int begin = end = 0;/* 开始循环求子序列和 */for (i = 0; i < n; i++){curSum = curSum + a[i];/* 与最大子序列和比较，更新最大子序列和 */if (curSum > maxSum){maxSum = curSum;end = i;}/* 动态规划部分，舍弃当前和为负的子序列 */if (curSum < 0){curSum = 0;begin = i + 1 >= n ? i : i + 1;}}return maxSum;}
二、求绝对值最大子序列和以及对应的区间
这个问题是对第一个问题的扩展，但比第一个问题复杂的多，O(N2)算法基本相同，也容易理解。
O(N2) C/C++实现：
1 int maxabssub(const int a[],int n) 2 { 3int sum, max, i, j, begin, end; 4begin = end = max = 0; 5for(i = 0;i < n;i++) 6{ 7 sum = 0; 8 for(j = i;j<n;j++) 9 {10 sum += a[j];11 printf("the second level loop %d loop sum = %d\n",j,sum);12 printf("the second level loop %d loop max = %d\n",j,max);13 if(abs(sum) > max)14 {15 max = abs(sum);16 begin = i;17 end = j;18 }19 }20 printf("the %d loop max = %d\n",i+1,max);21}22printf("--final-- Begin = %d, End = %d\n",begin,end);23return max;24 }
O(N)算法，在竹风抚荷塘同学的帮助下，顺利求解。思路其实很简单，绝对值最大的子序列和，要么是和最大，要么是和最小，类似问题一中O(N)算法，同时求每一个输入可能得到的最大和或最小和，再比较即可。下面是C/C++代码实现：
1 int maxAbsSubLinear(int a[], int n) 2 { 3int posiSum, negaSum, curSum, max, j, begin, end, posiBegin, posiEnd, negaBegin, negaEnd, flag; 4posiSum = negaSum = curSum = max = j = begin = end = posiBegin = posiEnd = negaBegin = negaEnd = flag = 0; 5 6for(j = 0;j < n;j++) 7{ 8 if(posiSum + a[j] > a[j]) 9 {10 posiSum += a[j];11 }12 else13 {14 posiSum = a[j];15 posiBegin = j;16 }17 if(negaSum + a[j] < a[j])18 {19 negaSum += a[j];20 }21 else22 {23 negaSum = a[j];24 negaBegin = j;25 }26 27 if( abs(posiSum) > abs(negaSum) )28 {29 curSum = abs(posiSum);30 posiEnd = j;31 flag = 1;32 }33 else34 {35 curSum = abs(negaSum);36 negaEnd = j;37 flag = 0;38 }39 40 if(curSum > max)41 {42 max = curSum;43 if(flag)44 {45 begin = posiBegin;46 end = posiEnd;47 }48 else49 {50 begin = negaBegin;51 end = negaEnd;52 }53 }54 55 printf("IN ABS LINEAR -- LOOP %d, posiSum = %d, negaSum = %d, curSum = %d, max=%d, begin = %d, end = %d\n", j+1, posiSum, negaSum, curSum, max, begin, end);56}57 58printf("--LINEAR final-- Begin = %d, End = %d\n",begin,end);59return max;60 }
再次感谢竹风抚荷塘同学。
