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

看板Prob_Solve作者 (小澤)時間16年前 (2008/05/14 23:16), 編輯推噓10(10推 0噓 6→)
留言16則, 7人參與, 最新討論串1/6 (看更多)
希望大大給點想法，今天寫題目的時候卡住了~ 講的越詳細越好~~ 使用者給一串整數，要找出它"連續"，且乘積最大者 例如: 5 -2 1 -1 最大 5*-2*1*-1 = 20 -1 2 5 最大 2*5 = 10 1 2 0 -3 -1 最大 -3*-1 = 3 大概是這樣~~ 先謝謝了~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.168.203.120
→
05/14 23:39, , 1F
嗯....終於被轉過來了　XD
05/14 23:39, 1F
→
05/14 23:58, , 2F
印像中做過這個ACM題目 是第幾題呢 我可以再做一遍
05/14 23:58, 2F
推
05/15 00:02, , 3F
11059
05/15 00:02, 3F
→
05/15 00:14, , 4F
哈~~還請大大幫忙了^^
05/15 00:14, 4F
推
05/15 02:18, , 5F
似乎要用 DP, 只是負數處理要小心
05/15 02:18, 5F
推
05/15 02:23, , 6F
沒錯, 一個 2n^2 的 table 就夠了, 複雜度 O(n*3)
05/15 02:23, 6F
推
05/15 03:56, , 7F
空間應該是 n*(n+1)/2 時間n*(n-1)/2 複雜度O(n^2)
05/15 03:56, 7F
推
05/15 04:52, , 8F
table 每填一格的時間只要 O(1) 嗎? 怎麼覺得是 O(n)?
05/15 04:52, 8F
推
05/15 04:53, , 9F
(口也, typo 我推的 O(n*3) 其實是 O(n^3) XD)
05/15 04:53, 9F
推
05/15 10:53, , 10F
N只有18呀 不論是 O(N^3) O(N^2) O(N) 甚至是 O(2^N)
05/15 10:53, 10F
→
05/15 10:53, , 11F
應該都可以在規定時間內將答案算出來吧～
05/15 10:53, 11F
→
05/15 11:23, , 12F
DP填table的時候可以利用已經計算出來的結果
05/15 11:23, 12F
→
05/15 11:23, , 13F
另外重複利用空間可減至 O(n)
05/15 11:23, 13F
推
05/15 17:44, , 14F
"利用已知條件" 不會是 O(1) 喔!
05/15 17:44, 14F
推
05/15 17:45, , 15F
嗯, 應該來回文才好說明, 先來睡覺了 Zzzzz
05/15 17:45, 15F
推
05/15 17:56, , 16F
咦, 沒錯, 確實是 O(1). 我原來用的遞迴式比較麻煩 @@
05/15 17:56, 16F
‣ 更多 polomoss 的文章
文章代碼(AID): #18Am9gk7 (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 6 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共6篇)
‣ 更多 polomoss 的文章
文章代碼(AID): #18Am9gk7 (Prob_Solve)