作者Domos (Domos)
看板java
标题Re: [问题] 连续整数，找出乘积最大?
时间Thu May 15 09:56:20 2008
看一下这个O(n)的演算法work不work
假设有n个数字要求max
我们把题目分解成n-1个数字
第n个数字如果为正，则求n-1的max
第n个数字如果为负，则求n-1的min
第n个数字如果为零，则求n-1的max
接下来用同样演算法去求出n-1的结果
以下是此演算法用DP实作:
a[] 选这个数字的MAX
b[] 不选这个数字的MAX
c[] 选这个数字的MIN
d[] 不选这个数字的MIN
e[] 此这个数字开始的值
数字存在num[]里
a[0]，b[0]，c[0]，d[0]，e[0]全部归零
for i = 1 ~ n
//以下x请改成num[i] 怕乱不这样写
a[i] = max(x * a[i-1],x * c[i-1],x * e[i-1])
b[i] = max(a[i-1],b[i-1],c[i-1],d[i-1],e[i-1])
c[i] = min(x * a[i-1],x * c[i-1],x * e[i-1])
d[i] = min(a[i-1],b[i-1],c[i-1],d[i-1],e[i-1])
e[i] = x
输出a[n],b[n],c[n],d[n],e[n]最大值
example:
0,1,3,-12,3,-1,4,0,-10,12,3,-2,-5,-7,-10,-1,3,2,-1,0
a b c d e
0 0 0 0 0 ini 这里出错了(或者说题目没定义)
如果可以选出空集合，那没错，如果一定要选出至少一个，
这里就得改成num[1]而非0
0 0 0 0 0 i=1
0 0 0 0 1 i=2
3 1 0 0 3 ...
0 3 -36 0 -12
0 3 -108 -36 3
108 3 -3 -108 -1
432 108 -432 -108 4
0 432 0 -432 0
0 432 0 -432 -10
0 432 -120 -432 12
36 432 -360 -432 3
720 432 -72 -432 -2
360 720 -3600-432 -5
... 懒的打了
d似乎可以省略，不过还是O(n)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.4.234
※ 编辑: Domos 来自: 140.112.30.84 (05/15 10:23)
1F：推 AppleFox:他是要求"连续"整数的乘积 你这样有考虑到连续吗? 05/15 14:57
2F：→ Domos:看仔细，想清楚 05/15 15:40
3F：推 teman:第n个数字如果为负，则求n-1的min，但是n-1的min是正数呢? 05/15 21:33
4F：→ Domos:感谢楼上提问，很好的问题 05/15 22:44
5F：→ Domos:min和max是连乘为+或-的最小值，n为正选用+的，负选用-的 05/15 22:47
※ 编辑: Domos 来自: 140.112.242.95 (05/15 22:55)