作者denehs (DE)
看板Prob_Solve
标题Re: [问题] 连续整数相乘，求乘积最大?
时间Mon May 19 12:06:10 2008
※ 引述《aknow (嘎嘎)》之铭言：
: 上面的都对
: 不过在这问题里有个很重要的地方
: 那就是
: 不看正负号的话, 整数都是越乘越大!!!
: 所以大略是
: 只要简单找一段偶数个负号
: 然後让这段越长就越好
: 不考虑一些boundary condition
: 只提大概
: 方法如下
: 看到0就切断 O(n)
: 所以现在有一段段没有0的
: 对於一段找最大的方法
: 1. 长度为1, 就是这个
: 2. 头到尾数一次
: 如果有偶数个负号
: 那这整个就是最大的
: 3. 若是奇数个负号
: 左边少几个让他变成偶数个
: 或是右边少几个
: 选一个乘起来最大的
: O(n)
反例:
-1, 1, 1, 1, 1, 1, -1, 1, -1, 100000
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.37
1F：推 ledia:到步骤 3, 左边少一个 -1, 应该就会找到最大值 ? 05/19 12:17
2F：→ ledia:反例应该是 -1 0 -1 05/19 12:18
3F：推 tkcn:推 这篇简单明了 05/19 13:50
4F：→ tkcn:囧 其实我是要推上一篇 (汗) 05/19 13:51
5F：推 aknow:感谢2F 有0的话 另外补上 但我想对於整个concept应该没问题 05/19 14:47
6F：→ aknow:当然还有例如step3 只有一个负号在最右边 从左边一直拿掉 05/19 14:49
7F：→ aknow:会整个拿到空 等等之类 这些都是boundary 不影响整个想法 05/19 14:49
8F：→ tkcn:有 0 的话就直接拆成两段小问题罗， 这样并不会增加复杂度 05/19 15:07