※ [本文轉錄自 java 看板 #18J16b9W ]
作者: tuju () 站內: java
標題: Re: [問題] 連續整數，找出乘積最大?
時間: Mon Jun 9 01:06:44 2008
好久的文章, 還是回一下..
我的演算是O(n)的演算法,
這裡的trick是因為整數絕對值只會愈乘愈大, 所以不用dynamic programming
初始三個變數
max = 0 //目前為止最大連乘積
product = 1 //連乘積
productAfterFirstMinus = 0; //第一個負號後的連乘積
每讀一個數字x進來{
if(x == 0){
product = 1;
productAfterFirstMinus = 0;
}else{
product *= x;
productAfterFirstMinus *= x;
max = Max(max, product, productAfterFirstMinus);
if(productAfterFirstMinus == 0 && x < 0){
productAfterFirstMinus = 1;
}
}
}
不知道這樣寫有沒有人看的懂..orz
※ 引述《Domos (Domos)》之銘言：
: 看一下這個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)