推 pika0923:其實只有整數的狀況不用特別把正零負挑出來也可以作 07/03 19:55
→ cckk3333:言之有理 07/03 20:10
※ 引述《dementia (妖精尾巴魔導士)》之銘言：
: 如果只討論思考邏輯的話…
: 0.5 檢查陣列長度，如果<2，則回傳錯誤訊息
: 1.用”0”切陣列
: {A,0,B} → {A} {B}
: 2.計算每個陣列長度。如果最長=1，則回傳0，結束
: 3.將長度1的全部踢除
: 4.如果有一個陣列長度>=4，則結果一定大於0，反之，應該蠻幹就可以了。然後，如果所
: 有的乘積都為負，則回傳0，否則回傳最大值，結束
: 5. 如果有一個陣列長度>=4，則對於每個陣列做以下計算
: 5-1 直接相乘。如果為正值，將這個值儲存，否則計算5-2～5-4
: 5-2 將陣列中第一個負數(含)前的數全踢除，如果剩餘的數長度>=2，則剩餘的相乘算乘
: 積
: 5-3 將陣列中最後一個負數(含)後的數全踢除， 如果剩餘的數長度>=2，則剩餘的相乘算
: 乘積
: 5-4 將5-2和5-3的結果儲存
: 6.將步驟5儲存的所有數值取最大值，回傳，結束。
一樣只想討論邏輯...
因為這篇把一些繁雜的情況考慮了 所以借用一下XD
只想討論5
目標是scan一次
var1, var2, var3 定義為
var1 存scan到n時相乘最大的數 (包含最後一個)
var2 存scan到n時相乘最小(最負)的數 (包含最後一個)
var3 存scan到n時相乘最大的數 (不一定包含最後一個)
初始化
n = 1 var1 = max(0,A[0]); (A for Array)
var2 = min(0,A[0]);
var3 = 夠小的數
假設到 n 時正確 考慮 n+1
var1 = max(var1,-var2) * ( (A[n+1] > 0) ? 1 : -1);
var2 = max(var1,-var2) * ( (A[n+1] > 0) ? -1: 1);
(同步)
接著 var3 = max(var3, var1)
var1 = max(var1,A[n+1]);
var2 = min(var2,A[n+1]);
這個主要是考慮A可能含有絕對值小於1的數(只有整數可以不用考慮)，要之後做
是要保證至少var3裡面的答案至少是兩個互乘
已盡量讓解法類似 maximum subarray XD
time: O(N) space: O(1)
---------------------------------------------------------
每次寫完這類題目總覺得會有很多漏洞XD
btw 互乘有沒有包含1個我覺得還是當場問問面試官，畢竟這種有點類似boundary的
情況本來就可能當作特例
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.111.101.142
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404387933.A.366.html