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); |