亚马逊电话面经 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

亚马逊电话面经

亚马逊电话面经# JobHunting - 待字闺中

l*t2011-05-20 07:05

1 楼

给一个数组里边都是整数求最大乘积的连续子数组

f*i2011-05-20 07:05

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*q2011-05-20 07:05

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*l2011-05-20 07:05

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*q2011-05-20 07:05

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*y2011-05-20 07:05

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 的大作中提到】

s*x2011-05-20 07:05

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*y2011-05-20 07:05

8 楼

题目都是整数

【在 s**x 的大作中提到】

: 0.1 * 0.2 < 0.1, so not correct