问题:有一个数组 31,-41,59,26,-53,58,97,-93,-23,84 。现在要求出它的连续子串的最大值。
比如,31,-41,59,26是它的一个连续的子串,他们的和为75。但是75并不是最大值,有一个子串 59,26,-53,58,97它们的和187才是最大的。

求解:《Programming Pearls》第77页开始一共给出了4种解法,前两种非常简单,是大多数人思考几分钟就能想出的方法,但是复杂度却很高,分别为O(n^3)和O(n^2)。后两种解法则非常巧妙,更神奇的是第四种方法居然只有线性复杂度O(n)!

解法1、解法2略。
解法3:分治法,复杂度为O(nlogn)。
分治法在结构上是递归的,在保证不改变原问题的条件下,将问题的规模减小,生成多个子问题,并多次递归调用自身来解决子问题,之后再将子问题的求解结果合并成原问题的解。

对于case1,我们只要比较ma和mb的大小就可以得出原数组的最大子串的和了,而对于case2只要把ma和mb相加即可。以上只是将问题一次分解的过程,我们还需要将问题再分解直到不能在分解或是能直接得出结果为止。
什么时候能直接得出结果?当子数组只有一个元素的时候,此时ma就是它本身(为负数时我们让它为0)。
因此,原数组的最大和= 2个子数组中最大和的较大者,或者,包括中间分界线的一段连续区域的和。
即,maxsum(orignial)=max(mc,maxsum(a),maxsum(b))
递归结束的条件是,子数组只有一个元素,如果是正返回它本身,为负返回0.

伪代码如下。

01 int maxsum(l,u)
02     if(l>u)
03       return 0;
04     if(l==u)
05       return max(0,x[l])
06     m=(l+u)/2
07     lmax=sum=0
08     for(i=m;i>=l,i)
09        sum+=x[i]
10        lmax=max(lmax,sum)
11     rmax=sum=0;
12     for i=(m,u]
13        sum+=x[i]
14        rmax=max(rmax,sum)
15 return max(lmax+rmax,maxsum(l,m),maxsum(m+1,u))

解法4:扫描法。一次扫描数组即可得出答案,复杂度O(n)。这种方法用文字描述不容易说清楚,下面用每一步运算的图示来表达。伪代码如下:

maxsofar=end=0;
for i=[0,n)
   end=max(end+x[i],0)
   maxsofar=max(maxsofar,end)

即使后面没有这样的值了,maxsofar中还保存了原来的最大和,有恃无恐。这里的一条重要原则是目前end的值必须>0,如果<0,则不用考虑,立刻放弃end目前的值,将它置为0,并且把end的指针指向58。

以此类推下去,最后可得正确的结果。

总的说来,解法4虽然原理很简单,还是自己很难想出来,甚至看了书上的讲解后还是存有疑惑,总觉得“这样子就可以了吗?在一些极端情况下不会出错吗?”即使写完这篇blog后,感觉我还是没有领会解法4的精髓。等到再读《编程珠玑》第2遍、第3遍以后,回过头来重新写读书笔记,也许有更多感悟。

10,728 views
Home

8 Comments so far

Leave a comment

Name(required)
Mail (required),(will not be published)
Website(recommended)

Fields in bold are required. Email addresses are never published or distributed.

Some HTML code is allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
URLs must be fully qualified (eg: http://blog.nlogn.cn),and all tags must be properly closed.

Line breaks and paragraphs are automatically converted.

Please keep comments relevant. Off-topic, offensive or inappropriate comments may be edited or removed.