※ 引述《cckk3333 (皓月)》之銘言：
: ※ 引述《dementia (妖精尾巴魔導士)》之銘言：
: : 如果只討論思考邏輯的話…
define:
N[i] = the input integer sequence with length n.
M[i] = max { N[j] * N[j+1] * ... * N[i-1] * N[i] | where j >= 0 and j <= i }
= max { M[i-1] * N[i], m[i-1] * N[i], N[i] }
m[i] = min { N[j] * N[j+1] * ... * N[i-1] * N[i] | where k >= 0 and k <= i }
= min { M[i-1] * N[i], m[i-1] * N[i], N[i] }
Max sub array product = max { M[i] | where i >= 0 and i < n }
init:
M[0] = N[0]
m[0] = N[0]
: : 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), 來自: 111.243.122.83
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404402373.A.2EE.html
※ 編輯: manlike (111.243.122.83), 07/03/2014 23:46:46