康瑞部落

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<n; i++){
            int product = 1;
            
            for(int j=i; j>=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<int> zeroPos;    //0的位置，0比较特殊
        //为了程序的简单，假设-1处和n处也是0
        zeroPos.push_back(-1);
        for(int i=0; i<n; i++){
            if(A[i]==0){
                zeroPos.push_back(i);
            }
        }
        zeroPos.push_back(n);
        int zeroNum = zeroPos.size();
        int result = A[0];
        for(int i=0; i<zeroNum-1; i++){
            int startPos = zeroPos[i]+1;
            int endPos = zeroPos[i+1]-1;
            if(endPos<startPos){
                continue;
            }
            int tempMax=1;
            for(int j=startPos; j<=endPos; j++){
                tempMax *= A[j];
            }
            //两边扫
            //左边递减
            int leftMax = tempMax;
            for(int j=startPos; j<endPos; j++){
                if(leftMax/A[j] >= 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; i<n; i++){
            int maxLocalCopy = maxLocal;
            
            maxLocal=max(A[i], maxLocal*A[i]);
            maxLocal=max(maxLocal, minLocal*A[i]);
            
            minLocal=min(A[i], minLocal*A[i]);
            minLocal=min(minLocal, maxLocalCopy*A[i]);
            
            result = max(result, maxLocal);
        }
        return result;
    }
    
    int max(int a, int b){
        return a>b?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

后面如何解释？求科普。