作者aknow (嘎嘎)
站内Prob_Solve
标题Re: [问题] 连续整数相乘，求乘积最大?
时间Mon May 19 10:09:55 2008
上面的都对
不过在这问题里有个很重要的地方
那就是
不看正负号的话, 整数都是越乘越大!!!
所以大略是
只要简单找一段偶数个负号
然後让这段越长就越好
不考虑一些boundary condition
只提大概
方法如下
看到0就切断 O(n)
所以现在有一段段没有0的
对於一段找最大的方法
1. 长度为1, 就是这个
2. 头到尾数一次
如果有偶数个负号
那这整个就是最大的
3. 若是奇数个负号
左边少几个让他变成偶数个
或是右边少几个
选一个乘起来最大的
O(n)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.166.200.179
※ 编辑: aknow 来自: 218.166.200.179 (05/19 10:10)
1F：→ neverfly:第三个step，O(n)做的完吗？ 05/19 14:43
2F：→ aknow:2n=O(n) 05/19 14:44