推 michael0728n:This algorithm is better! 學習了~~ 07/03 20:34
推 dementia:學到了 07/03 23:09
推 twsh:推 07/03 23:35
※ 引述《sleeper0121 (sleeper)》之銘言：
: 今天去面試，裡面有題題目是這樣:
: 寫個函式，傳個整數陣列進去，陣列裡面的整數可以是正數、負數或 0
: 請回傳一個陣列裡面相鄰互乘的最大整數值
: 例如: [2 , -7 , 0 , 2 , 3 , 8 , -6 , 5]
: 就是 2 * 3 * 8 = 48
: 再一個例子: [-2 , 0 , 3 , 5 , -7]
: 就是 3 * 5 = 15
: 請問這題思考邏輯大概是怎樣呢?
: 當下沒解出來，害我回家後還一直再想 XD
想了一個作法 開兩個陣列存 "含有這個位子及以左的最大值和最小值"
叫他amax和amin好了
由於這題目一定是整數 在這裡絕對值要變大就要一路乘下去 不然就不乘(0的狀況)
所以 amax[x]會是 ar[x], ar[x]*amax[x-1], ar[x]*amin[x-1]三者之一
同理 amin[x]也會出現在其中
而所求的區段一定有個結尾 也一定被某個amax[x]算到 所以最後求amax的最大值即可
--
寫了一個ruby code(最近正在練習XD)
就算當作演算法的pseudo code應該也不會太難讀
ar = gets.split(' ').map(&:to_i) #讀陣列
amin, amax = [ar[0]], [ar[0]] #初始化
(1...(ar.length)).each do |x| #迴圈,把剩下的跑完
amin << [ar[x],ar[x]*amin[x-1],ar[x]*amax[x-1]].min #見上述
amax << [ar[x],ar[x]*amin[x-1],ar[x]*amax[x-1]].max #見上述
end
p amax.max
--
前文的2 -7 0 2 3 8 -6 5 -1是可以正確求解的
(是說這題比較像是prob_solve版的業務 雖然說那邊人也不太多就是^^")
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.127.4.157
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404379102.A.0D1.html
補上長度至少2的作法
"長度至少2"的最佳解 會由 "尾端一個數"串上"前面至少一個數的最佳解"求得
bmax ar[x] amax[x-1],amin[x-1]
因此只需要在後面加上幾行修正即可 code如下
ar = gets.split(' ').map(&:to_i)
amin, amax = [ar[0]], [ar[0]]
(1...(ar.length)).each do |x|
amin << [ar[x],ar[x]*amin[x-1],ar[x]*amax[x-1]].min
amax << [ar[x],ar[x]*amin[x-1],ar[x]*amax[x-1]].max
end
bmax = []
(1...(ar.length)).each do |x|
bmax << [ar[x]*amin[x-1],ar[x]*amax[x-1]].max
end
p bmax.max
※ 編輯: pika0923 (59.127.4.157), 07/03/2014 19:34:32