Re: [問題] 連續整數，找出乘積最大?
自己挑戰自己 XD 上面的那個有點太複雜，其實不用這樣搞的
大概應該像這樣:
Set = X1,X2 ..... Xn
1. 將零當成 separator，分成好幾個 segment，然後每一個 segment Xi... Xj:
2. 從 Xi 往後查閱最近的負數，假設為 Xh。同樣由 Xj 往前查閱最近的負數，
假設為 Xg
2a. 若 Xh == Xg，把此 segment 分成兩份: (Xi.. Xh-1), (Xh+1.. Xj)
每一份計算乘積取比較大的那個，跳到 9
2b. 若沒有 Xh Xg，把整個 segment 的乘積作為 local Maximum，跳到 9
3. 計算 Xi .. Xh = P(front) 的乘積
4. 計算 Xh+1 .... Xg-1 = P(middle) 的乘積
5. 計算 Xg ... Xj = P(last) 的乘積
6. 計算 P(front) * P(middle) * P(last) 的乘積
6a. 若為正數，把它當成此 segment 的 localMaximum
6b. 若為負數，選取 P(front) 和 P(last) 中比較小的那一個，為 P(min)
並計算 P(middle) * P(min) 作為此 segment 的最大積
7. 完成所有 segment 後，比較所有 segment 找出最大值 Ｘ
8. 若Ｘ為負數而數列中有 0，取 0 (XD)
完了 :P
(用心寫的話，效能可以壓在 O(2n) 之下)
--
《為了要得到真相，就要向原 PO 伸圖》
那就是伸圖魔人的沒圖沒真相原則，那時我們堅信那就是逼逼死的真實
靠么，圖咧？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 147.8.130.225
※ 編輯: superlubu 來自: 147.8.130.225 (05/14 19:27)
※ 編輯: superlubu 來自: 218.102.77.18 (05/14 22:18)
討論串 (同標題文章)
完整討論串 (本文為第 4 之 12 篇)：