作者polomoss (小澤)
站內Prob_Solve
標題[問題] 連續整數相乘，求乘積最大?
時間Wed May 14 23:16:57 2008
希望大大給點想法，今天寫題目的時候卡住了~
講的越詳細越好~~
使用者給一串整數，要找出它"連續"，且乘積最大者
例如:
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
1F：→ pthuang:嗯....終於被轉過來了 XD 05/14 23:39
2F：→ bleed1979:印像中做過這個ACM題目 是第幾題呢 我可以再做一遍 05/14 23:58
3F：推 ckclark:11059 05/15 00:02
4F：→ polomoss:哈~~還請大大幫忙了^^ 05/15 00:14
5F：推 march20:似乎要用 DP, 只是負數處理要小心 05/15 02:18
6F：推 march20:沒錯, 一個 2n^2 的 table 就夠了, 複雜度 O(n*3) 05/15 02:23
7F：推 tkcn:空間應該是 n*(n+1)/2 時間n*(n-1)/2 複雜度O(n^2) 05/15 03:56
8F：推 march20:table 每填一格的時間只要 O(1) 嗎? 怎麼覺得是 O(n)? 05/15 04:52
9F：推 march20:(口也, typo 我推的 O(n*3) 其實是 O(n^3) XD) 05/15 04:53
10F：推 DJWS:N只有18呀 不論是 O(N^3) O(N^2) O(N) 甚至是 O(2^N) 05/15 10:53
11F：→ DJWS:應該都可以在規定時間內將答案算出來吧～ 05/15 10:53
12F：→ tkcn:DP填table的時候可以利用已經計算出來的結果 05/15 11:23
13F：→ tkcn:另外重複利用空間可減至 O(n) 05/15 11:23
14F：推 march20:"利用已知條件" 不會是 O(1) 喔! 05/15 17:44
15F：推 march20:嗯, 應該來回文才好說明, 先來睡覺了 Zzzzz 05/15 17:45
16F：推 march20:咦, 沒錯, 確實是 O(1). 我原來用的遞迴式比較麻煩 @@ 05/15 17:56