作者superlubu (叔叔你人真好)
看板java
標題Re: [問題] 連續整數，找出乘積最大?
時間Wed May 14 15:43:08 2008
大概應該像這樣:
Set = X1,X2 ..... Xn
1. 將零當成 separator，分成好幾個 segment，然後每一個 segment Xi... Xj:
2. 統計 Xi 至 Xj 中負數的數量:
2a. 若負數的數量為偶數，將整個 segment 乘積作為
此 segment 的最大積 (Local maximum)，跳到 9
2b. 若負數的數量為 1，將這個 segment 在負數的位置
分成兩個 segment，比較左右兩個的乘積比較大，
成為 Xi... Xj 的 Local maximum，跳到 9
3c. 若負數的數量為基數並且不等於 1，到 3
3. 從 Xi 往後查閱最近的負數，假設為 Xh。同樣由 Xj 往前查閱最近的負數，
假設為 Xg
4. 計算 Xi .. Xh = P(front) 的乘積，一定是負數
5. 計算 Xh+1 .... Xg-1 = P(middle) 的乘積，同樣是負數
6. 計算 Xg ... Xj = P(last) 的乘積，也是負數
7. 比較 P(front) 和 P(last)，
取比較小的那一個，為 P(min)
8. 計算 P(middle) * P(min)，作為此 segment 的最大積
9. 完成所有 segment 後，比較所有 segment 找出最大值 Ｘ
10. 若Ｘ為負數而數列中有 0，取 0 (XD)
完成了，原來比想像中簡單 XDrz
PS. 也不太簡單... 剛才忘了只有一個負數的特例要再重算...
另外若是要知道真正的 MaxProduct(X1... Xn) 的 range
則要記著每個 segment 的位置，遇到只有一個負數的特
例時也要把 segment 的 range 重置...
--
《為了要得到真相，就要向原 PO 伸圖》
那就是伸圖魔人的沒圖沒真相原則，那時我們堅信那就是逼逼死的真實
靠么，圖咧？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 147.8.130.225
※ 編輯: superlubu 來自: 147.8.130.225 (05/14 16:31)