※ [本文转录自 java 看板 #18J16b9W ]
作者: tuju () 站内: java
标题: Re: [问题] 连续整数，找出乘积最大?
时间: Mon Jun 9 01:06:44 2008
好久的文章, 还是回一下..
我的演算是O(n)的算法,
这里的trick是因为整数绝对值只会愈乘愈大, 所以不用dynamic programming
初始三个变量
max = 0 //目前为止最大连乘积
product = 1 //连乘积
productAfterFirstMinus = 0; //第一个负号后的连乘积
每读一个数字x进来{
if(x == 0){
product = 1;
productAfterFirstMinus = 0;
}else{
product *= x;
productAfterFirstMinus *= x;
max = Max(max, product, productAfterFirstMinus);
if(productAfterFirstMinus == 0 && x < 0){
productAfterFirstMinus = 1;
}
}
}
不知道这样写有没有人看的懂..orz
※ 引述《Domos (Domos)》之铭言：
: 看一下这个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)
这样是错的， [-1,-2,-3,-4,-5,-6,-7] 这样会错