[LeetCode] Maximum Product Subarray
Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.
解题思路：
1、最基本的办法，枚举， 需要的时间复杂度为O(n^2)，产生超时。代码如下：
class Solution {
public:
int maxProduct(int A[], int n) {
int result=A[0];
for(int i=1; i=0; j--){
product *= A[j];
result = max(result, product);
}
}
return result;
}
int max(int a, int b){
return a>b?a:b;
}
};
2、两边扫描逐步递减法。这是我第一想到的办法，对于一串非0的整数数组元素，先计算他的全部元素的乘积。然后分别从两边扫描，将乘积除以扫描的元素。若结果大于原来的乘积，则继续，否则停止。就题目的例子来说，原来的乘积为-48。从左边开始扫描，-48/2=-24，大于原来的乘积，乘积置为-24，继续扫描。-24/3=-8大于-24，乘积置为-8，继续。-8/-2=4大于-8，乘积置为4，这里剩下一个元素，不再扫描（因为再除的话肯定为1），因此从左边扫描最大的乘积为4。同理，从右边扫描最大的乘积为6。结果取较大值。下面是代码：
class Solution {
public:
int maxProduct(int A[], int n) {
vector zeroPos; //0的位置，0比较特殊
//为了程序的简单，假设-1处和n处也是0
zeroPos.push_back(-1);
for(int i=0; i= leftMax){
leftMax /= A[j];
}else{
break;
}
}
result = max(result, leftMax);
//右边递减
int rightMax = tempMax;
for(int j=endPos; j>startPos; j--){
if(rightMax/A[j]>=rightMax){
rightMax /= A[j];
}else{
break;
}
}
result = max(result, rightMax);
}
if(zeroNum>2){ //表明原数组内有至少一个0
result=max(result, 0);
}
return result;
}
int max(int a, int b){
return a>b?a:b;
}
};
3、2的办法不容易想到，方法不成体系。可以考虑动态规划。这是我事先未想到的，至今也不是太明白。但大体思路是记录局部的最大值和局部最小值。因为最小值（倘若为负数）乘以一个负数的话，就会转化为最大值。代码如下：
class Solution {
public:
int maxProduct(int A[], int n) {
if(n==0){
return 0;
}
if(n==1){
return A[0];
}
int maxLocal;
int minLocal;
int result;
result = maxLocal = minLocal = A[0];
for(int i=1; ib?a:b;
}
int min(int a, int b){
return a>b?b:a;
}
};
假如数组元素为-4，-3，-2，-1，0，-1，minLocal和maxLocal的取值分别为：
maxLocal: -4 12 8 24 0 0
minLocal: -4 -4 -24 -8 0 -1
后面如何解释？求科普。
原文作者：；如有侵权，请联系管理员删除。
