※ 引述《sleeper0121 (sleeper)》之銘言：
: 今天去面試，裡面有題題目是這樣:
: 寫個函式，傳個整數陣列進去，陣列裡面的整數可以是正數、負數或 0
: 請回傳一個陣列裡面相鄰互乘的最大整數值
: 例如: [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5]
: 就是 2 * 3 * 8 = 48
: 再一個例子: [-2 , 0 , 3 , 5 , -7]
: 就是 3 * 5 = 15
: 請問這題思考邏輯大概是怎樣呢?
: 當下沒解出來，害我回家後還一直再想 XD
今天在 facebook 釣出高手，我想應該是最正確的演算法了
先從左邊乘過去，再從右邊乘回來，遇 0 重算，取最大值
以 { 2, -7, 0, 2, 3, 8, -6, 5 } 來說
左邊乘過去會得到 2, -14, 0, 2, 6, 48, -288, -1440
右邊乘回來會得到 5, -30, -240, -720, -1440, 0, -7, -14
幾個值，得到最大值 48
我的實作 http://ideone.com/dmOEEO
沒判斷子陣列只有一個元素的情況，不過題目也沒定義所以就算了 :p

-2, 10, 10, -2 呢？

400 呀

有趣

好妙

讚

(y)

推 再加點判斷還可以只要單向算過去就好

這作法還不錯 要看單向版本可以看我那篇

推

好方法!

Good

好厲害！！！

引用一樓-2 10 10 -2 -3 呢?(-2 -20 -200 400 -1200) max600忘了還有右邊乘回來的

Push

我那篇有右邊乘回來同時把last value做動態變動的

樓上 你那篇跑[-2, 2, -2]好像不會算出8?

真的也 那篇只有回原Po的解決方式 看來要加判斷式應該還是能在O(n)內解決http://jsfiddle.net/ERKxh/3/ 這是有多一些設定的但是還是不能解決全部算完是正的 晚點來看

0 999 999 999 999 999 999 999 999 999 999 999 999 999 0

要解過大的數字 那只能建質數表 因式分解 最終才用大數

...不是這樣吧 ... 這個例子0的位置讓他歪打正著

[-0.5, 2, 2, -0.5] 就會算錯喔喔喔我搞錯如果題目只有整數就是對的

-1,-2,-3,-4,-5,-6,-7

bruceX: 遇到零就重算SansWord, 計算過程中取大的值, 所以反方向算回來就可以holydc: 這...這...這好像是我在你facebook的解法!!!pika0923: 你的是單向沒錯可是你有考慮過你每次都要做很多次乘積和三數取大/小雖然大家都是O(n), 可是我這邊實際跑出數字應該是不會比較慢?!

這個方法改一下就可以單向了乘出負數時若之前沒有就記下來若之前有就除掉之前記下的數, 這樣就不必反向算回來實際速度會不會比較快就...要測看看 @@更進一步, 只有零的前一個是負數時需要去除, 中間不必這樣應該就確定會比較快

剛剛看了一下lovdkkkk, 理論上你的做法應該會快些而且也才是真的one parse(1 parse比2 parse複雜的情況其實就當他不是好了...)

perfact!

現在才看到yp回的 嚴格說起來用ruby作已經比c慢20倍了XD而最大最小值其實算是為了閱讀方便如果玩過這類演算法競賽就會知道 在同一個語言的實作下其實答案對量級對之後實作差異非常小甚至有時候把一堆判斷式省掉還會比較快加一堆判斷式有時候是省小錢花大錢的作法我還蠻喜歡你這篇的作法就是因為概念簡單正確XD

以 C 來說的話, 判斷相對於乘/除法是可以忽略的(除非判斷的對象本身需要其它運算)真的想再省的話, 只要多記一組數 (3 個 int)就可以把處理和原本判斷遇 0 重算的部份寫在一起以及在廻圈結束後再處理最後一個數更正, 多記一個 int 應該就夠了想成把處理前一個負數包成 function遇零及廻圈結束後再 call 一下就好, 只要多記前一個算的值, 位置則可以直接用推的再更正, 應該也不用多記, 在算下一個之前先處理就好

pika0923: XD 因為我只想得出奇怪的解法XD不過是說 這其實有個複雜的證明在後面...理論上可以用數學歸納法證明...只要證明1~3個數字的數列然後最後在推廣他應該就可以lovdkkkk: 我自己實際上去看應該是多記一個負數就可