作者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
推 ledia:到步驟 3, 左邊少一個 -1, 應該就會找到最大值 ? 05/19 12:17
→ ledia:反例應該是 -1 0 -1 05/19 12:18
推 tkcn:推 這篇簡單明瞭 05/19 13:50
→ tkcn:囧 其實我是要推上一篇 (汗) 05/19 13:51
推 aknow:感謝2F 有0的話 另外補上 但我想對於整個concept應該沒問題 05/19 14:47
→ aknow:當然還有例如step3 只有一個負號在最右邊 從左邊一直拿掉 05/19 14:49
→ aknow:會整個拿到空 等等之類 這些都是boundary 不影響整個想法 05/19 14:49
→ tkcn:有 0 的話就直接拆成兩段小問題囉， 這樣並不會增加複雜度 05/19 15:07