Re: [問題] 連續整數相乘，求乘積最大?
看板Prob_Solve (計算數學 Problem Solving)作者aknow (嘎嘎)時間16年前 (2008/05/19 10:09)推噓0(0推 0噓 2→)留言2則, 2人參與討論串5/6 (看更多)
上面的都對
不過在這問題裡有個很重要的地方
那就是
不看正負號的話, 整數都是越乘越大!!!
所以大略是
只要簡單找一段偶數個負號
然後讓這段越長就越好
不考慮一些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)
→
05/19 14:43, , 1F
05/19 14:43, 1F
→
05/19 14:44, , 2F
05/19 14:44, 2F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
