推 lovdkkkk:ancient power XD 07/03 23:17
※ 編輯: johnlinvc (220.137.13.133), 07/04/2014 02:32:31
推 frouscy:ancient power! 07/04 17:26
※ 引述《ck574b027 (荒圍!定厝!賊!妹!)》之銘言：
: ※ 引述《pika0923 (宜安)》之銘言：
: : 想了一個作法 開兩個陣列存 "含有這個位子及以左的最大值和最小值"
: : 叫他amax和amin好了
: : 由於這題目一定是整數 在這裡絕對值要變大就要一路乘下去 不然就不乘(0的狀況)
: : 所以 amax[x]會是 ar[x], ar[x]*amax[x-1], ar[x]*amin[x-1]三者之一
: : 同理 amin[x]也會出現在其中
: : 而所求的區段一定有個結尾 也一定被某個amax[x]算到 所以最後求amax的最大值即可
: 這個除了直觀、O(n)之外，還可以順便算最小值，於是我用 scala 寫一個遞迴版本。
: 假設題目一定要連續相乘，單一數字不算，長度 1 以下回傳 Nil
: https://gist.github.com/bendwarn/4b69495194fb047b978e
Haskell 的 一行文
mulMax = maximum . fst . foldl
(\(maxs@(max:_), mins@(min:_)) x ->
((maximum $ map (*x) [1,min,max]) : maxs,
(minimum $ map (*x) [1,min,max]) : mins)) ([0],[0])
mulMax [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5] # 48
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.137.13.133
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404400481.A.92E.html