Re: [問題] Maximum problem
※ 引述《joyboytoy (亂來 XD)》之銘言:
: 這種解法的效率在於, 之前算過的東西不用重算
: 譬如c1的値不必去作X1+X2+X3+X4, 而只要 b1+X4 即可
: 等到數列變長, 節省的計算也就越多
: 長度為n的數列只需要 (n-1)^2/2 次的相加
: 以上是用dynamic programming去作的
: 不過不知道有沒有更快的解法 @__@
你的解法time complexity 為 O(n^2) , 效率不是說很好
其實你可以根據前面 citronrisky 板友的想法稍加改變
即可找出 linear 的解法
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.216.102
討論串 (同標題文章)
完整討論串 (本文為第 3 之 5 篇):
Inference 近期熱門文章
3
13
PTT遊戲區 即時熱門文章
17
56
44
76