作者Domos (Domos)
看板java
標題Re: [問題] 連續整數，找出乘積最大?
時間Thu May 15 09:56:20 2008
看一下這個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)
1F：推 AppleFox:他是要求"連續"整數的乘積 你這樣有考慮到連續嗎? 05/15 14:57
2F：→ Domos:看仔細，想清楚 05/15 15:40
3F：推 teman:第n個數字如果為負，則求n-1的min，但是n-1的min是正數呢? 05/15 21:33
4F：→ Domos:感謝樓上提問，很好的問題 05/15 22:44
5F：→ Domos:min和max是連乘為+或-的最小值，n為正選用+的，負選用-的 05/15 22:47
※ 編輯: Domos 來自: 140.112.242.95 (05/15 22:55)