在做 LeetCode OJ，有题做不出，答案也看不懂，觉得自己很蠢怎么办
kevinyoung · 2014-10-25 16:52:51 +08:00 · 15404 次点击这是一个创建于 3683 天前的主题，其中的信息可能已经有所发展或是发生改变。
挑到maximum subarray这题了： https://oj.leetcode.com/problems/maximum-subarray/
想了半天写不出，去google发现有wiki的页面，但是上面给的答案简洁则已，自己居然连为什么是对的都看不出，上面还说这个解法是简单的动态规划，根本不明白啊，觉得自己太蠢了，是不是该收拾收拾回家种田好了
想了半天写不出，去google发现有wiki的页面，但是上面给的答案简洁则已，自己居然连为什么是对的都看不出，上面还说这个解法是简单的动态规划，根本不明白啊，觉得自己太蠢了，是不是该收拾收拾回家种田好了
第 1 条附言 · 2014-10-25 19:44:29 +08:00
感谢各位的回复，吐槽完就看明白答案了，然后顺便把分冶的给写了，但是我的python版超内存限制了，就没再看了。
算法导论我也看了，动态规划还没讲明白先被例子给搅迷糊了，这书感觉适合当reference，学习算法的话推荐Udi Manber的算法引论： http://book.douban.com/subject/1436134/
同样是讲动态规划，一页纸就说完了，例子也清楚的多，关键是书本详细介绍了如何用数学归纳没法设计分析算法，真熟练了的话可以砍瓜切菜，我这才刚开始，所以做题还是被虐....
@mitcc 推荐了数据结构与算法分析——c语言描述，听说不错，但还没来得及看 http://book.douban.com/subject/1139426/
@icylogic 推荐了普林斯顿在coursera上开的算法课，第一部分已经完结，第二部分还有5天开课，但是也太龟毛了，上完就不给看存档了。我自己抓了一份放在度盘上，刚想分享一下的，但是试了四次都是直接被抽，蛋都碎了...
算法导论我也看了，动态规划还没讲明白先被例子给搅迷糊了，这书感觉适合当reference，学习算法的话推荐Udi Manber的算法引论： http://book.douban.com/subject/1436134/
同样是讲动态规划，一页纸就说完了，例子也清楚的多，关键是书本详细介绍了如何用数学归纳没法设计分析算法，真熟练了的话可以砍瓜切菜，我这才刚开始，所以做题还是被虐....
@mitcc 推荐了数据结构与算法分析——c语言描述，听说不错，但还没来得及看 http://book.douban.com/subject/1139426/
@icylogic 推荐了普林斯顿在coursera上开的算法课，第一部分已经完结，第二部分还有5天开课，但是也太龟毛了，上完就不给看存档了。我自己抓了一份放在度盘上，刚想分享一下的，但是试了四次都是直接被抽，蛋都碎了...
第 2 条附言 · 2014-10-25 19:48:59 +08:00
 |
1
jsonline 2014-10-25 17:07:39 +08:00 via Android  1
先看算法导论吧
|
 |
2
sethverlo 2014-10-25 17:35:42 +08:00 via iPhone 1
不建议算法导论，想省事儿就搜下动态规划相关的博客。
|
 |
3
hustlike 2014-10-25 17:51:00 +08:00 1
看不懂不一定是因为蠢，因为很多人都不会。网上教的学算法的方法我觉得基本上都是不切实际的，比如沙发。首先期望要放低一点。。
|
 |
4
txx 2014-10-25 17:54:41 +08:00 1
沒經過大腦寫了一個 簡單粗暴地 轉移方程...
f(i) 表示 0~i 且選擇第i位的最優值 f(i) = max(A[i], f(i-1) + A[i]) f(0) = A[0] f 數組中最大的數 即為所求.... |
 |
5
binux 2014-10-25 18:01:25 +08:00 1
这题也挺逗的，你想到 O(N) 之后你用分治，我以为分治有多巧妙呢，想半天都是 O(NlogN)，结果看讨论，分治就是 O(NlogN) 的。。
|
 |
6
mitcc 2014-10-25 18:23:19 +08:00 1
对于这一题，我推荐你看一下Mark Allen Weiss写的那本《数据结构与算法分析——C语言描述》的第2章中的最大子序列求和问题，从O(n^3)到O(n^2)到O(nlgn),最后到O(n),循序渐进，当时我看到这儿时，被这种讲法给震到了，如此简洁明了，毫无理解障碍，尤其是从O(n^3)到O(n^2),他会告诉你怎么省掉一些开销。
反观国内某人写的某本高校广泛使用的数据结构，看得头疼，代码完全不能运行，不说也罢，偏题了，不好意思。 |
 |
7
xcv58 2014-10-25 18:39:27 +08:00 via iPad 1
先写简单的程序把测试用例弄出来些。然后一个例子一个例子地看，手工怎么算。然后尝试扩展成程序，再考虑如何优化。
|
 |
8
jox 2014-10-25 18:41:04 +08:00 1
lz不要灰心啊，这种算法题有点像脑筋急转弯，也有点像锻炼身体，多练练就好了
|
 |
9
icylogic 2014-10-25 18:51:13 +08:00 1
同在刷 leetcode, 这道题以前在 @mitcc 提到的那本书里见过.
不过这本书讲得有点简单, 类似 K&R 这个级别的, 现在就着公开课在慢慢看 clrs , 虽然一开始有点晕, 看到第三章开始有点习惯了...... 有很多人推荐 Coursera 的那个普林斯顿开的 Algorithm, 对应的书是 <算法 第四版> 有中文版. |
 |
11
kevinyoung OP @txx 你可以去试试，不对...
|
|
12
txx 2014-10-25 20:09:30 +08:00
@kevinyoung 我表示提交 AC 了啊~
|
 |
14
wizardforcel 2014-12-03 16:28:05 +08:00 via Android
这题是联机算法，我也没搞懂。
sum = max(sum + a[i], a[i]); maxsum = max(sum, maxsum); |
Select Language