算法探讨——再议经典算法问题：求最大子序列和、绝对值最大子序列和以及其区间VIP免费

算法探讨——再议经典算法问题：求最大子序列和、绝对值最大子序列和以及其区间给定任一数字序列，如{-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++实现：1intmaxsub(constinta[],intn)2{3intsum,max,i,j,begin,end;4begin=end=max=0;5for(i=0;imax)14{15max=sum;16begin=i;17end=j;18}19}20printf("the%dloopmax=%d\n",i+1,max);21}22printf("--final--Begin=%d,End=%d\n",begin,end);23returnmax;24}循环结束后，begin与end的值即对应的区间。O(N)算法：动态规划思想，也称on-linealgorithm，即，对于每一个输入，不依赖于后面输入，对每一个输入，立即计算其结果，并保存，然后与后续输入进行比较，若和变大，产生更新。若和总是变小，丢弃之前的输入。C/C++实现：intmaxsublinear(constinta[],intn){inti;intcurSum=0;/*当前序列和*/intmaxSum=0;/*最大序列和*/intbegin=end=0;/*开始循环求子序列和*/for(i=0;imaxSum){maxSum=curSum;end=i;}/*动态规划部分，舍弃当前和为负的子序列*/if(curSum<0){curSum=0;begin=i+1>=n?i:i+1;}}returnmaxSum;}二、求绝对值最大子序列和以及对应的区间这个问题是对第一个问题的扩展，但比第一个问题复杂的多，O(N2)算法基本相同，也容易理解。O(N2)C/C++实现：1intmaxabssub(constinta[],intn)2{3intsum,max,i,j,begin,end;4begin=end=max=0;5for(i=0;imax)14{15max=abs(sum);16begin=i;17end=j;18}19}20printf("the%dloopmax=%d\n",i+1,max);21}22printf("--final--Begin=%d,End=%d\n",begin,end);23returnmax;24}O(N)算法，在竹风抚荷塘同学的帮助下，顺利求解。思路其实很简单，绝对值最大的子序列和，要么是和最大，要么是和最小，类似问题一中O(N)算法，同时求每一个输入可能得到的最大和或最小和，再比较即可。下面是C/C++代码实现：1intmaxAbsSubLinear(inta[],intn)2{3intposiSum,negaSum,curSum,max,j,begin,end,posiBegin,posiEnd,negaBegin,negaEnd,flag;4posiSum=negaSum=curSum=max=j=begin=end=posiBegin=posiEnd=negaBegin=negaEnd=flag=0;56for(j=0;ja[j])9{10posiSum+=a[j];11}12else13{14posiSum=a[j];15posiBegin=j;16}17if(negaSum+a[j]abs(negaSum))28{29curSum=abs(posiSum);30posiEnd=j;31flag=1;32}33else34{35curSum=abs(negaSum);36negaEnd=j;37flag=0;38}3940if(curSum>max)41{42max=curSum;43if(flag)44{45begin=posiBegin;46end=posiEnd;47}48else49{50begin=negaBegin;51end=negaEnd;52}53}5455printf("INABSLINEAR--LOOP%d,posiSum=%d,negaSum=%d,curSum=%d,max=%d,begin=%d,end=%d\n",j+1,posiSum,negaSum,curSum,max,begin,end);56}5758printf("--LINEARfinal--Begin=%d,End=%d\n",begin,end);59returnmax;60}