作者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)