l****o
发帖数: 135 | 1 Maximum Product Subarray
找到这个solution比较简洁，但是不很明白，谁能帮忙解释一下？为啥不需要考虑负数？
http://leetcodesolution.blogspot.com/2014/09/leetcode-maximum-p |
J*****a
发帖数: 46 | 2 它自己解释的已经很清楚了 不错的思路 不过不可以处理浮点数
另一种做法是维护以 i 结尾的最大负数和最大正数 可以处理浮点数 |
l*****a
发帖数: 14598 | 3 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]);
}
数？
【在 l****o 的大作中提到】
: Maximum Product Subarray
: 找到这个solution比较简洁，但是不很明白，谁能帮忙解释一下？为啥不需要考虑负数？
: http://leetcodesolution.blogspot.com/2014/09/leetcode-maximum-p
|
J*****a
发帖数: 46 | 4 明明是可以 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*****8
发帖数: 3635 | 5 那个网页的解法为啥不能处理浮点数？
【在 J*****a 的大作中提到】
: 它自己解释的已经很清楚了 不错的思路 不过不可以处理浮点数
: 另一种做法是维护以 i 结尾的最大负数和最大正数 可以处理浮点数
|
J*****a
发帖数: 46 | 6 因为会有 (-1, 1) 之间的数
【在 j*****8 的大作中提到】
: 那个网页的解法为啥不能处理浮点数？
|
c********6
发帖数: 33 | 7 这个2，3，-2, 4会得到24吧
感觉dp没法线性时间解决这种连续的问题
【在 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]);
: }
:
: 数？
|
l*****a
发帖数: 14598 | 8 let me know how u get that?
thanks
【在 c********6 的大作中提到】
: 这个2，3，-2, 4会得到24吧
: 感觉dp没法线性时间解决这种连续的问题
|
l****o
发帖数: 315 | 9 如果是奇数个负数，排除第一个负数和之前所有的数，乘剩下的，同理对最后一个负数。
偶数个和0的都很好处理。 |
c********6
发帖数: 33 | 10 不好意思，是我看错了~~~
【在 l*****a 的大作中提到】
: let me know how u get that?
: thanks
|
|
|
y**********a
发帖数: 824 | 11
数。
对的，blog 上的算法就是对这个的改进。
【在 l****o 的大作中提到】
: 如果是奇数个负数，排除第一个负数和之前所有的数，乘剩下的，同理对最后一个负数。
: 偶数个和0的都很好处理。
|
q********c
发帖数: 1774 | 12 写了一个只用一个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 的大作中提到】
: Maximum Product Subarray
: 找到这个solution比较简洁，但是不很明白，谁能帮忙解释一下？为啥不需要考虑负数？
: http://leetcodesolution.blogspot.com/2014/09/leetcode-maximum-p
|
b*********s
发帖数: 115 | 13 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******g
发帖数: 3616 | 14 刚看到这题，试着写了下，成功过了，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;
}
return res;
}
不过感觉leetcode这题测试也不是很详细，做乘法应该还要检查overflow的问题吧,显
然我的代码还没考虑这点。 |
l*****a
发帖数: 14598 | 15
为什么这句不用 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******g
发帖数: 3616 | 16 弱问这两种写法差别在哪？可读性？
【在 l*****a 的大作中提到】
:
: 为什么这句不用 res=Math.max(Pmax,res)
|
b******g
发帖数: 3616 | 17 这个solution的思路挺有意思的，但感觉复杂度上并没有比dp更有优势？而且理解起来
也没有dp这么直观似乎。特别是两个方向的循环扫描计算prod来涵盖p=0和p<0的情况还
是需要仔细想下才明白的。
数？
【在 l****o 的大作中提到】
: Maximum Product Subarray
: 找到这个solution比较简洁，但是不很明白，谁能帮忙解释一下？为啥不需要考虑负数？
: http://leetcodesolution.blogspot.com/2014/09/leetcode-maximum-p
|
h*******e
发帖数: 1377 | |
w*******i
发帖数: 186 | |
b******g
发帖数: 3616 | 20 这个blog解答的code略长啊。。。。。
直接被第二个思路的code长度吓尿了-_-!
【在 w*******i 的大作中提到】
: http://blog.csdn.net/whuwangyi/article/details/39577455
|
