Re: [問題] 連續整數，找出乘積最大?
看一下這個O(n)的演算法work不work
假設有n個數字要求max
我們把題目分解成n-1個數字
第n個數字如果為正，則求n-1的max
第n個數字如果為負，則求n-1的min
第n個數字如果為零，則求n-1的max
接下來用同樣演算法去求出n-1的結果
以下是此演算法用DP實作:
a[] 選這個數字的MAX
b[] 不選這個數字的MAX
c[] 選這個數字的MIN
d[] 不選這個數字的MIN
e[] 此這個數字開始的值
數字存在num[]裡
a[0]，b[0]，c[0]，d[0]，e[0]全部歸零
for i = 1 ~ n
//以下x請改成num[i] 怕亂不這樣寫
a[i] = max(x * a[i-1],x * c[i-1],x * e[i-1])
b[i] = max(a[i-1],b[i-1],c[i-1],d[i-1],e[i-1])
c[i] = min(x * a[i-1],x * c[i-1],x * e[i-1])
d[i] = min(a[i-1],b[i-1],c[i-1],d[i-1],e[i-1])
e[i] = x
輸出a[n],b[n],c[n],d[n],e[n]最大值
example:
0,1,3,-12,3,-1,4,0,-10,12,3,-2,-5,-7,-10,-1,3,2,-1,0
a b c d e
0 0 0 0 0 ini 這裡出錯了(或者說題目沒定義)
如果可以選出空集合，那沒錯，如果一定要選出至少一個，
這裡就得改成num[1]而非0
0 0 0 0 0 i=1
0 0 0 0 1 i=2
3 1 0 0 3 ...
0 3 -36 0 -12
0 3 -108 -36 3
108 3 -3 -108 -1
432 108 -432 -108 4
0 432 0 -432 0
0 432 0 -432 -10
0 432 -120 -432 12
36 432 -360 -432 3
720 432 -72 -432 -2
360 720 -3600-432 -5
... 懶的打了
d似乎可以省略，不過還是O(n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.234
※ 編輯: Domos 來自: 140.112.30.84 (05/15 10:23)
推
05/15 14:57, , 1F
05/15 14:57, 1F
→
05/15 15:40, , 2F
05/15 15:40, 2F
推
05/15 21:33, , 3F
05/15 21:33, 3F
→
05/15 22:44, , 4F
05/15 22:44, 4F
→
05/15 22:47, , 5F
05/15 22:47, 5F
※ 編輯: Domos 來自: 140.112.242.95 (05/15 22:55)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 10 之 12 篇)：