请大牛解释一下leetcode新题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请大牛解释一下leetcode新题

请大牛解释一下leetcode新题# JobHunting - 待字闺中

h*e2014-09-24 07:09

1 楼

【以下文字转载自 Joke 讨论区】
发信人: twols (蓝领小小生), 信区: Joke
标题: 性浪标题
发信站: BBS 未名空间站 (Wed Sep 1 00:42:22 2010, 美东)
中国男篮vs波多黎各

l*o2014-09-24 07:09

2 楼

Maximum Product Subarray
找到这个solution比较简洁，但是不很明白，谁能帮忙解释一下？为啥不需要考虑负数？
http://leetcodesolution.blogspot.com/2014/09/leetcode-maximum-p

c*52014-09-24 07:09

3 楼

波多野结衣....

J*a2014-09-24 07:09

4 楼

它自己解释的已经很清楚了不错的思路不过不可以处理浮点数
另一种做法是维护以 i 结尾的最大负数和最大正数可以处理浮点数

A*D2014-09-24 07:09

5 楼

2008年从事AV出演。波多野结衣最初是拍摄“东京流仪62”被发掘的，这位绝品美女因
为出色的外表以及超正的身材，就让影迷们眼睛为之一亮，胸型浑圆自然，加上她那冷
艳的脸孔、白的如瓷器的滑嫩肌肤、纤细的腰身、修长的美腿，还有做爱时的娃娃呻吟
音，出道没多久马上爆红，还赢得了‘暗黑界林志玲’的封号。波多野结衣在日本名气
普通，但在华人地区享有盛名。
2010年波多野结衣在演出的作品中宣布了自己即将结婚的消息，但究竟是影片剧情的安
排，还是她真的即将步入礼堂，尚未获得证实。

l*a2014-09-24 07:09

6 楼

how about this one?
min[0]=max[0]=a[0];
for(int i=1;imax[i]=max(a[i],max[i-1]*a[i],min[i-1]*a[i]);
min[i]=min(a[i],max[i-1]*a[i],min[i-1]*a[i]);
result=Math.max(result,max[i]);
}

数？

【在 l****o 的大作中提到】

: Maximum Product Subarray
: 找到这个solution比较简洁，但是不很明白，谁能帮忙解释一下？为啥不需要考虑负数？
: http://leetcodesolution.blogspot.com/2014/09/leetcode-maximum-p

J*a2014-09-24 07:09

7 楼

明明是可以 O(1) 空间的

【在 l*****a 的大作中提到】

: how about this one?
: min[0]=max[0]=a[0];
: for(int i=1;i: max[i]=max(a[i],max[i-1]*a[i],min[i-1]*a[i]);
: min[i]=min(a[i],max[i-1]*a[i],min[i-1]*a[i]);
: result=Math.max(result,max[i]);
: }
:
: 数？

j*82014-09-24 07:09

8 楼

那个网页的解法为啥不能处理浮点数？

【在 J*****a 的大作中提到】

: 它自己解释的已经很清楚了不错的思路不过不可以处理浮点数
: 另一种做法是维护以 i 结尾的最大负数和最大正数可以处理浮点数

J*a2014-09-24 07:09

9 楼

因为会有 (-1, 1) 之间的数

【在 j*****8 的大作中提到】

: 那个网页的解法为啥不能处理浮点数？

c*62014-09-24 07:09

10 楼

这个2，3，-2, 4会得到24吧
感觉dp没法线性时间解决这种连续的问题

【在 l*****a 的大作中提到】

l*a2014-09-24 07:09

11 楼

let me know how u get that?
thanks

【在 c********6 的大作中提到】

: 这个2，3，-2, 4会得到24吧
: 感觉dp没法线性时间解决这种连续的问题

l*o2014-09-24 07:09

12 楼

如果是奇数个负数，排除第一个负数和之前所有的数，乘剩下的，同理对最后一个负数。
偶数个和0的都很好处理。

c*62014-09-24 07:09

13 楼

不好意思，是我看错了~~~

【在 l*****a 的大作中提到】

: let me know how u get that?
: thanks

y*a2014-09-24 07:09

14 楼

数。
对的，blog 上的算法就是对这个的改进。

【在 l****o 的大作中提到】

: 如果是奇数个负数，排除第一个负数和之前所有的数，乘剩下的，同理对最后一个负数。
: 偶数个和0的都很好处理。

q*c2014-09-24 07:09

15 楼

写了一个只用一个for循环的，通过了
class Solution {
public:
int maxProduct(int A[], int n) {
int currMax = 1, currMin = 1, maxAll = INT_MIN;
for(int i = 0; i < n; ++i) {
if(A[i] >= 0) {
currMax = currMax<=0?A[i]:currMax*A[i];
currMin = currMin*A[i];
}
else {
int temp = currMax;
currMax = max(currMin*A[i], A[i]);
currMin = min(temp*A[i], A[i]);
}
if(maxAll < currMax)
maxAll = currMax;
}
return maxAll;
}
};

数？

【在 l****o 的大作中提到】

b*s2014-09-24 07:09

16 楼

def maxProduct(self, a):
if not a:
return 1
res = max_e = min_e = a[0]
for x in a[1:]:
candidates = [max_e * x, min_e * x, x]
max_e = max(candidates)
min_e = min(candidates)
res = max(res, max_e)
return res

b*g2014-09-24 07:09

17 楼

刚看到这题，试着写了下，成功过了，C++:
int maxProduct(int A[], int n) {
if(n<1) return 0;
int res, Pmax, Pmin;
res = Pmax = Pmin = A[0];
for(int i=1; iint temp = max(max(Pmax*A[i],Pmin*A[i]),A[i]);
Pmin = min(min(Pmax*A[i],Pmin*A[i]),A[i]);
Pmax = temp;
res = Pmax>res ? Pmax : res;
}
return res;
}
不过感觉leetcode这题测试也不是很详细，做乘法应该还要检查overflow的问题吧,显
然我的代码还没考虑这点。

l*a2014-09-24 07:09

18 楼

为什么这句不用 res=Math.max(Pmax,res)

【在 b******g 的大作中提到】

: 刚看到这题，试着写了下，成功过了，C++:
: int maxProduct(int A[], int n) {
: if(n<1) return 0;
: int res, Pmax, Pmin;
: res = Pmax = Pmin = A[0];
: for(int i=1; i: int temp = max(max(Pmax*A[i],Pmin*A[i]),A[i]);
: Pmin = min(min(Pmax*A[i],Pmin*A[i]),A[i]);
: Pmax = temp;
: res = Pmax>res ? Pmax : res;

b*g2014-09-24 07:09

19 楼

弱问这两种写法差别在哪？可读性？

【在 l*****a 的大作中提到】

:
: 为什么这句不用 res=Math.max(Pmax,res)

b*g2014-09-24 07:09

20 楼

这个solution的思路挺有意思的，但感觉复杂度上并没有比dp更有优势？而且理解起来
也没有dp这么直观似乎。特别是两个方向的循环扫描计算prod来涵盖p=0和p<0的情况还
是需要仔细想下才明白的。

数？

【在 l****o 的大作中提到】

h*e2014-09-24 07:09

21 楼

O(1) 一个pass 就可以拉。