题目可以看这里: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就在这里,书里认为如果重合了,还是一样的。
显然这里是不对的,只要最小数组里有负数,重合就会导致负数被多次计算,求得的和肯定不是最大的。
因为只要去掉负数,就一定比没去掉负数所得的子数组和要大。
所以改进的应该,如果首尾连接的数组求最大子数组和,当遇到重合情况,要求出连续最小和的串,然后刨除掉。
《编程之美》中“求数组最大子数组的和”的bug
《编程之美》热门书评
-
迟来的书评和感想──给喜爱编程的朋友
181有用 3无用 Milo 2010-02-24
这本书我读了两遍,分別是两个印次。读第一遍是这书刚出版的时候买的第一版,读第二遍是因为最近认识了本书作者及编辑,我说以前看到本书的一些小错处,出版社就寄了第7次印刷本给我。在新年前花了一个星期把书尽量仔细地看了一遍,发现这印次仍有一些小问题及程序的bugs,已连同其他意见回馈给作者。 我其实不太喜欢...
-
我所了解的微软面试
81有用 0无用 蓬山远 2012-11-11
2014 05 22本文是一年半以前写的了。这一年半之间微软发生了很大的变化,我自己也发生了很大的变化,时过境迁,世殊事异。大家就看个乐子好了,不宜再当作经验去套用了。------------------------------------------------------------------...
-
数据结构和算法是程序的根本——为什么?!
49有用 0无用 bluedavy 2009-07-10
转自博客。应该是差不多两个月前收到了这本书,一直到最近才抽出时间来看了下,这本书的开篇的第一题现在基本已经成了经典中的经典了,相信很多人都因为这个控制CPU使用率的题从而买了这本书的,在我自己看过这本书后我同时相信买了这本书的人应该会觉得非常的值得,要写出合理实现需求、高性能以及大数据量的程序,数据...
-
一本未看完的书 一段未走完的旅途
21有用 3无用 Dear Al 2010-03-29
答应了Lisa写这篇书评 买这本书是大四的时候了 大学接近尾声 作为一名计算机软件方向的本科毕业生 我们学校竟未开过一门类似于算法导论之类的课程 哦 对了 是有一门类似的数据结构 它和Linux是我大学阶段最喜欢的专业课了 不过那些内容 唉 那时候很喜欢在CSDN上瞎晃 于是便迷恋上了高纳德 接受了...
-
享受用程序语言思维的乐趣
20有用 0无用 gaomiao 2009-07-17
闲暇时喜欢翻书,但也许是习惯了屏幕前飞快的阅读速度,如今看书已不像原先啃书那般细致。阅读时往往对引出道理的故事很感兴趣,而到了讲道理的细节,便一扫而过。然而最近在读的《编程之美》一书,却是无论如何也无法像读其他书籍那样浮光掠影般翻看,而是字斟句酌,生怕遗漏了半点细节。如果说在看《算法导论》这样的经典...