题目可以看这里:http://www.cnblogs.com/xinz/archive/2011/10/10/2205232.html
《编程之美》 中提到 “求数组最大子数组的和”这一题目,
(图1)
脑快手快的同学写一个 10 行的程序就把这个问题搞定了。
我们还把这个问题扩展到二维, 例如:
(图2)
我还问过一些同学, 如果数组首尾相连, 像一个轮胎一样, 又怎么办呢? 这些同学也给出了漂亮的答案, 并且用 SilverLight/WPF 给画了出来:
(图3)
好,设想我们有一张纸带,两面都写满了像 [图2] 那样的数字, 我们把纸带的一端扭转, 和另一端接起来, 构成一个莫比乌斯环 (Möbius Strip).
(图4 – wikipedia)
我想尽管这个纸带扭了一下, 但是上面还是有数组, 还是有最大子数组的和, 对么? 在求最大子数组的和之前, 我们用什么样的数据结构来表示这些数字呢? 你可以用 Java, C, C#, 或其他语言的数据结构来描述这个莫比乌斯环上的数组。数据结构搞好了, 算法自然就有了。
书中的bug在于,当一维数组是首尾相连的,该如何求得最大子数组的。
当数组首尾不相连时,也可以通过分治法,将数组两边,分别求最大和,再求出中间(跨越分界点)的最大和,再比较。
分别求最大和的时候就容易想到动态规划的方法。
但是首尾相连时,书里认为一样可以分开求两边,如果数组两边绕回来没有重合,就还是按分治法的思路做。
如果重合了呢?bug就在这里,书里认为如果重合了,还是一样的。
显然这里是不对的,只要最小数组里有负数,重合就会导致负数被多次计算,求得的和肯定不是最大的。
因为只要去掉负数,就一定比没去掉负数所得的子数组和要大。
所以改进的应该,如果首尾连接的数组求最大子数组和,当遇到重合情况,要求出连续最小和的串,然后刨除掉。