Re: [問題] 連續整數相乘，求乘積最大?

看板Prob_Solve作者 (DE)時間16年前 (2008/05/19 12:06), 編輯推噓3(3推 0噓 5→)
留言8則, 3人參與, 最新討論串6/6 (看更多)
※ 引述《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
推
05/19 12:17, , 1F
到步驟 3, 左邊少一個 -1, 應該就會找到最大值 ?
05/19 12:17, 1F
→
05/19 12:18, , 2F
反例應該是 -1 0 -1
05/19 12:18, 2F
推
05/19 13:50, , 3F
推 這篇簡單明瞭
05/19 13:50, 3F
→
05/19 13:51, , 4F
囧 其實我是要推上一篇 (汗)
05/19 13:51, 4F
推
05/19 14:47, , 5F
感謝2F 有0的話 另外補上 但我想對於整個concept應該沒問題
05/19 14:47, 5F
→
05/19 14:49, , 6F
當然還有例如step3 只有一個負號在最右邊 從左邊一直拿掉
05/19 14:49, 6F
→
05/19 14:49, , 7F
會整個拿到空 等等之類 這些都是boundary 不影響整個想法
05/19 14:49, 7F
→
05/19 15:07, , 8F
有 0 的話就直接拆成兩段小問題囉， 這樣並不會增加複雜度
05/19 15:07, 8F
‣ 更多 denehs 的文章
文章代碼(AID): #18CFopTN (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 6 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共6篇)
‣ 更多 denehs 的文章
文章代碼(AID): #18CFopTN (Prob_Solve)