l********t
发帖数: 123 | 1 给一个数组 里边都是整数 求最大乘积的连续子数组 | f*********i
发帖数: 197 | 2 x = a0*a1...*an
find x1 = a0*a1...ai where ai is the first negative element
find x2 = an*an-1...aj where aj is the last negative element
if x is positive, then x,
if x is negative, then max(x/x1, x/x2,x1/ai,x2/aj)
if there are 0 in the array, then divide the array into different groups by
0 and applied the way mentioned above to each group.
it is an O(n) approach. | m**q
发帖数: 189 | 3 想到了一个DP解，不过要复杂一些:
pos[i]: 以i结尾的最大绝对值乘积的正值
neg[i]: 以i结尾的最大绝对值乘积的负值
pe[i]: 存在以i结尾的正值
ne[i]: 存在以i结尾的负值
max: 当前连续乘积的最大值
pos[i-1] * a[i] (a[i] > 0 && pe[i-1] != 0)
pos[i] = neg[i-1] * a[i] (a[i] < 0 && ne[i-1] != 0)
a[i] (otherwise)
pos[i-1] * a[i] (a[i] < 0 && pe[i-1] != 0)
neg[i] = neg[i-1] * a[i] (a[i] > 0 && ne[i-1] != 0)
a[i] (otherwise)
pe[i] = pos[i] > 0;
ne[i] = neg[i] < 0;
max = MAX(max, pos[i]);
可以优化到只需要O(1)的额外空间，时间复杂度也是O(n)。
by
【在 f*********i 的大作中提到】
: x = a0*a1...*an
: find x1 = a0*a1...ai where ai is the first negative element
: find x2 = an*an-1...aj where aj is the last negative element
: if x is positive, then x,
: if x is negative, then max(x/x1, x/x2,x1/ai,x2/aj)
: if there are 0 in the array, then divide the array into different groups by
: 0 and applied the way mentioned above to each group.
: it is an O(n) approach.
| d*******l
发帖数: 338 | 4 int MaxProduct(int a[], int n)
{
int maxp = 0, maxn = 0;
int ans = 0;
for(int i = 0; i < n; i++) {
if(!a[i]) maxp = maxn = 0;
else if(a[i] > 0) {
maxp = max(maxp*a[i], a[i]);
maxn = a[i]*maxn;
} else {
int t = maxn;
maxn = min(maxp*a[i], a[i]);
maxp = a[i]*t;
}
ans = max(ans, maxp);
}
return (n==1)?a[0]:ans;
}
【在 m**q 的大作中提到】
: 想到了一个DP解，不过要复杂一些:
: pos[i]: 以i结尾的最大绝对值乘积的正值
: neg[i]: 以i结尾的最大绝对值乘积的负值
: pe[i]: 存在以i结尾的正值
: ne[i]: 存在以i结尾的负值
: max: 当前连续乘积的最大值
:
: pos[i-1] * a[i] (a[i] > 0 && pe[i-1] != 0)
: pos[i] = neg[i-1] * a[i] (a[i] < 0 && ne[i-1] != 0)
: a[i] (otherwise)
| m**q
发帖数: 189 | 5 赞！ 这个真简洁
【在 d*******l 的大作中提到】
: int MaxProduct(int a[], int n)
: {
: int maxp = 0, maxn = 0;
: int ans = 0;
: for(int i = 0; i < n; i++) {
: if(!a[i]) maxp = maxn = 0;
: else if(a[i] > 0) {
: maxp = max(maxp*a[i], a[i]);
: maxn = a[i]*maxn;
: } else {
| g**********y
发帖数: 14569 | 6 对有0的情况，象你说的divide-and-conqueror.
没有0时，
1. 扫描a, 生成负数子集neg
2. neg数为偶数，return product of a[]
3. neg数是奇数，return max(product of a[0..最后一个负数前],
product of a[第一个负数后..N-1]
by
【在 f*********i 的大作中提到】
: x = a0*a1...*an
: find x1 = a0*a1...ai where ai is the first negative element
: find x2 = an*an-1...aj where aj is the last negative element
: if x is positive, then x,
: if x is negative, then max(x/x1, x/x2,x1/ai,x2/aj)
: if there are 0 in the array, then divide the array into different groups by
: 0 and applied the way mentioned above to each group.
: it is an O(n) approach.
| s**x
发帖数: 7506 | 7 0.1 * 0.2 < 0.1, so not correct
【在 g**********y 的大作中提到】
: 对有0的情况，象你说的divide-and-conqueror.
: 没有0时，
: 1. 扫描a, 生成负数子集neg
: 2. neg数为偶数，return product of a[]
: 3. neg数是奇数，return max(product of a[0..最后一个负数前],
: product of a[第一个负数后..N-1]
:
: by
| g**********y
发帖数: 14569 | 8 题目都是整数
【在 s**x 的大作中提到】
: 0.1 * 0.2 < 0.1, so not correct
| m******n
发帖数: 6327 | 9 不对，0 -3 0 -3 0
必须返回这5个数
【在 g**********y 的大作中提到】
: 对有0的情况，象你说的divide-and-conqueror.
: 没有0时，
: 1. 扫描a, 生成负数子集neg
: 2. neg数为偶数，return product of a[]
: 3. neg数是奇数，return max(product of a[0..最后一个负数前],
: product of a[第一个负数后..N-1]
:
: by
| g**********y
发帖数: 14569 | 10 为什么？不就是返回0？
【在 m******n 的大作中提到】
: 不对，0 -3 0 -3 0
: 必须返回这5个数
| m******n
发帖数: 6327 | 11 要求返还连续子集
【在 g**********y 的大作中提到】
: 为什么？不就是返回0？
| g**********y
发帖数: 14569 | 12 最大乘积的连续子集，0，和{0,-3,0,-3,0}不是一样的吗？
【在 m******n 的大作中提到】
: 要求返还连续子集
| m******n
发帖数: 6327 | 13 最大乘积一样，子集不一样。
所以按0分割成子集，有漏洞。
【在 g**********y 的大作中提到】
: 最大乘积的连续子集，0，和{0,-3,0,-3,0}不是一样的吗？
|
|
