在做 LeetCode OJ，有题做不出，答案也看不懂，觉得自己很蠢怎么办

[kevinyoung]

挑到maximum subarray这题了： https://oj.leetcode.com/problems/maximum-subarray/

想了半天写不出，去google发现有wiki的页面，但是上面给的答案简洁则已，自己居然连为什么是对的都看不出，上面还说这个解法是简单的动态规划，根本不明白啊，觉得自己太蠢了，是不是该收拾收拾回家种田好了

[jsonline]

先看算法导论吧

[sethverlo]

不建议算法导论，想省事儿就搜下动态规划相关的博客。

[hustlike]

看不懂不一定是因为蠢，因为很多人都不会。网上教的学算法的方法我觉得基本上都是不切实际的，比如沙发。首先期望要放低一点。。

[txx]

沒經過大腦寫了一個 簡單粗暴地 轉移方程...

f(i) 表示 0~i 且選擇第i位的最優值

f(i) = max(A[i], f(i-1) + A[i])
f(0) = A[0]

f 數組中最大的數 即為所求....

[binux]

这题也挺逗的，你想到 O(N) 之后你用分治，我以为分治有多巧妙呢，想半天都是 O(NlogN)，结果看讨论，分治就是 O(NlogN) 的。。

[mitcc]

对于这一题，我推荐你看一下Mark Allen Weiss写的那本《数据结构与算法分析——C语言描述》的第2章中的最大子序列求和问题，从O(n^3)到O(n^2)到O(nlgn),最后到O(n),循序渐进，当时我看到这儿时，被这种讲法给震到了，如此简洁明了，毫无理解障碍，尤其是从O(n^3)到O(n^2),他会告诉你怎么省掉一些开销。

反观国内某人写的某本高校广泛使用的数据结构，看得头疼，代码完全不能运行，不说也罢，偏题了，不好意思。

[xcv58]

先写简单的程序把测试用例弄出来些。然后一个例子一个例子地看，手工怎么算。然后尝试扩展成程序，再考虑如何优化。

[jox]

lz不要灰心啊，这种算法题有点像脑筋急转弯，也有点像锻炼身体，多练练就好了

[icylogic]

同在刷 leetcode, 这道题以前在 @mitcc 提到的那本书里见过.

不过这本书讲得有点简单, 类似 K&R 这个级别的, 现在就着公开课在慢慢看 clrs , 虽然一开始有点晕, 看到第三章开始有点习惯了......

有很多人推荐 Coursera 的那个普林斯顿开的 Algorithm, 对应的书是 <算法 第四版> 有中文版.

[qiukun]

@mitcc 我校某本教材就是这么讲的

[kevinyoung]

@txx 你可以去试试，不对...

[txx]

@kevinyoung 我表示提交 AC 了啊~

[qiukun]

@binux 分治在并行条件下有优势呀

[wizardforcel]

这题是联机算法，我也没搞懂。

sum = max(sum + a[i], a[i]);
maxsum = max(sum, maxsum);

[vjnjc]

@txx 嘿哥们我在面试的时候遇到这个题了。结果当然是我没做出来 0 0