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

[polomoss (小澤)]

希望大大給點想法，今天寫題目的時候卡住了~
講的越詳細越好~~



使用者給一串整數，要找出它"連續"，且乘積最大者

例如:
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
→ pthuang:嗯....終於被轉過來了　XD
→ bleed1979:印像中做過這個ACM題目 是第幾題呢 我可以再做一遍
推 ckclark:11059
→ polomoss:哈~~還請大大幫忙了^^
推 march20:似乎要用 DP, 只是負數處理要小心
推 march20:沒錯, 一個 2n^2 的 table 就夠了, 複雜度 O(n*3)
推 tkcn:空間應該是 n*(n+1)/2  時間n*(n-1)/2  複雜度O(n^2)
推 march20:table 每填一格的時間只要 O(1) 嗎? 怎麼覺得是 O(n)?
推 march20:(口也, typo 我推的 O(n*3) 其實是 O(n^3) XD)
推 DJWS:N只有18呀  不論是 O(N^3) O(N^2) O(N)  甚至是 O(2^N)
→ DJWS:應該都可以在規定時間內將答案算出來吧～
→ tkcn:DP填table的時候可以利用已經計算出來的結果
→ tkcn:另外重複利用空間可減至 O(n)
推 march20:"利用已知條件" 不會是 O(1) 喔!
推 march20:嗯, 應該來回文才好說明, 先來睡覺了 Zzzzz
推 march20:咦, 沒錯, 確實是 O(1). 我原來用的遞迴式比較麻煩 @@