作者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