作者Redsuns (ZZZzzz...)
看板Inference
标题Re: [问题] Maximum problem
时间Thu Nov 18 17:22:59 2004
※ 引述《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