《编程之美》中“求数组最大子数组的和”的bug

题目可以看这里：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就在这里，书里认为如果重合了，还是一样的。

显然这里是不对的，只要最小数组里有负数，重合就会导致负数被多次计算，求得的和肯定不是最大的。

因为只要去掉负数，就一定比没去掉负数所得的子数组和要大。




所以改进的应该，如果首尾连接的数组求最大子数组和，当遇到重合情况，要求出连续最小和的串，然后刨除掉。