作者superlubu (叔叔你人真好)
看板java
标题Re: [问题] 连续整数，找出乘积最大?
时间Wed May 14 17:09:01 2008
自己挑战自己 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)