Maximum Product Subarray

algorithm

涉及到公式请到作业部落查看：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.

问题来自于Leetcode:Maximum Product Subarray

问题分析

• 简单来说就是在一个数组中找到一个子数组，使得这个子数组的元素的乘积是所有子数组中最大的。
• 拿到这个问题，我们看一下和Maximum Subarray类似，但是又有点不同，类似的地方在求解的是一个子数组$\{A_{i},A_{i+1} \dots A_{j} \}$，使得$\prod_{t=i}^{j}A_t$最大。不同的地方在于，这个求解的是子数组各个元素的乘积，我们知道，数组中如果有负数那么有可能存在两个负数相乘，得到的乘积最大，这种情况，和最大子数组不同，最大子数组要相加就可以了。并不需要多考虑这种负数相乘的情况，也就是说，这个题比最大子数组的题多了一种情况，那么我们就把多出的这种情况考虑进来就可以了。

解决方案

1.动态规划方法

• 按着我们求解最大子数组的思路，来看我们要记录一下以$A_{j}$结尾的最大子数组的乘积，假设用$Smax_{j}$表示，还要记录到$A_{j}$为止的最大子数组的乘积，假设用$Max_{j}$表示。同时,还要考虑负数相乘的情况。那么我们就记录一个以$A_{j}$结尾的最小子数组的乘积，假设用$Smin_{j}$表示，如果遇到$A_{j} \lt 0$这种情况，在整个过程当中 $Smax_j \ge Smin_j$。那么我们直接用$A_{j}$乘以最小子数组$Smin_{j-1}$和$A_{j}$,$Smax_{j-1} \cdot A_{j}$进行比较。取最大的那个。在$A_j \gt 0$的时候，我们也按着这种思路来去三个中最大的那个，那么就不会遗漏任何一种情况了。同时也需要按着跟新最大值的方式来跟新最小值。
• 下面给出具体的数学表达式。
  $$Max_{j} = \left\{ \begin{array}{rcl} Smax_{j-1} & & A_j \gt A_{j}\cdot Smax_{j-1} \&\& A_j \gt 0\\ A_{j} \cdot Smin_{j-1} & & A_j \lt 0 \&\& Smin_{j-1}\cdot A_j \gt A_j\\ A_j & & A_j \gt Smax_{j-1} \cdot A_j \&\& A_j \gt Smin_{j-1} \cdot A_j \end{array} \right.$$
• 简化一下使用max和min函数把多种情况放在一起，这样就可以不用考虑$A_j$的正负了。
  $$Smax_j = max( A_j\cdot Smax_{j-1} ,A_j, A_j \cdot Smin_{j-1} )\\ Smin_j = min( A_j\cdot Smin_{j-1} ,A_j, A_j \cdot Smax_{j-1} )\\ Max_j = max(Max_{j-1},Smax_{j})$$
• 下面是按着上面的思路写下的代码。存在优化的地方。

int maxProduct_O3n(vector<int>& nums) {
    int n = nums.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return nums[0];
    vector<int> smax(n,1);
    vector<int> smin(n,1);
    vector<int> dp(n,0);
    smax[0] = nums[0];
    smin[0] = nums[0];
    Max[0] = nums[0];
    for(int i=1;i<n;++i){
        smax[i] = max( max(smax[i-1]*nums[i],nums[i]),smin[i-1]*nums[i] );
        smin[i] = min ( min(smin[i-1]*nums[i],nums[i]) , smax[i-1]*nums[i]);
        Max[i] = max(Max[i-1],smax[i]);
    }
    return Max[n-1];
}

• 可以看出来时间复杂度为$O(n)$,空间复杂度为$O(3n)=O(n)$.
• 上面的代码部分明显存在可以优化的部分，比如$Max$数组，$Max_{j-1}$只是在求$Max_{j}$的时候使用到，所以可以用一个变量$dp$代替，在求解$A_j$的时候,$dp$代表到$A_{j-1}$为止的最大子数组乘积的值，并交换更新。
• 其次，对于$Smax,Smin$两个数组也是，在求$Smax_{j},Smin_{j}$的时候只用到了$Smax_{j-1},Smin_{j-1}$，之前的$j-2,\dots 0$并没有用到。所以分别用两个变量$Smax,Smin$代替即可(命名重复(-__-)b)，下面给出优化后的代码。优化后的代码在Leetcode上面跑的比上面的代码快了很多。

int maxProduct(vector<int>& nums) {
    int n = nums.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return nums[0];
    int smax;
    int smin;
    int dp;
    smax = nums[0];
    smin= nums[0];
    dp = nums[0];
    for(int i=1;i<n;++i){
        int tmax = max (  max(smax * nums[i],nums[i]) ,smin * nums[i]);
        smin= min ( min(smin*nums[i],nums[i]) , smax*nums[i]);
        smax = tmax;
        dp = max(dp,smax);
    }
    return dp;
}

• 时间复杂度仍然为$O(n)$,空间复杂度为$O(1)$.

2.分治的方法

• 由于这个题是最大子数组和的变形，还没有涉及到扩展到二维数组的情况，二维情况后续会写。所以最大子数组和里面有个分治的算法，在这里面也可以使用。主要的点是，我们要分别在跨越中点的子数组的时候，我们需要考虑到左边最小值和右边最小值，在两者都是负数的情况下，可能乘积也是最大的，所以在求跨越中点的子数组的时候，不仅仅要求的最大的，还要同时求得最小的，并且在取最大值得时候，要考虑左右两个最小的子数组（为负数乘以负数）乘积的情况。
• 下面给出基于分治算法的递归实现。

int maxProduct(vector<int> & nums) {
    int n = nums.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return nums[0];
    return maxProduct_help(nums,0,n-1);
}
int maxProduct_help(vector<int> &nums,int begin,int end){
    if (begin == end)
        return nums[end];
    int mid = (begin + end) >> 1;
     /**左边子数组的最大值子数组乘积的值*/
    int smax_left = maxProduct_help(nums,begin,mid);
     /**右边子数组的最大值子数组乘积的值*/
    int smax_right= maxProduct_help(nums,mid+1,end);
    /**跨越中点的最大值子数组乘积的值*/
    int max_cross = maxCrossMid(nums,begin,end);
    return max(max(smax_left,smax_right),max_cross);
}
/*maxCrossMid函数的时间复杂度实际为O(n)*/
int maxCrossMid(vector<int> & nums,int begin,int end){
    if(begin == end)
        return nums[end];
    int mid = (begin + end ) >> 1;
    int max_left = nums[mid];
    int min_left = nums[mid];
    int max_right = nums[mid+1];
    int min_right = nums[mid+1];
    int sum = 1;
     /*计算以mid结尾的最大(小)的子数组乘积，左边子数组*/
    for(int i=mid;i>=begin;--i){
        sum *= nums[i];
        if(sum > max_left )
            max_left = sum;
        if(sum < min_left)
            min_left = sum;
    }
    sum = 1;
    /*计算以mid+1开始的最大(小)的子数组乘积，右边子数组*/
    for(int i=mid+1;i<=end;++i){
        sum *= nums[i];
        if(sum > max_right)
            max_right = sum;
        if(sum < min_right)
            min_right = sum;
    }
    /*左边最小和右边最小乘积结果可能是比左边最大和右边最大成绩结果要大*/
    return max(min_left*min_right,max_left*max_right);
}

• 在求解的过程中我们也可以看到$min\_left \le max\_left$,$min\_right \le max\_right$,所以并不需要考虑交叉乘积的值最大。
• 时间复杂度$T(n) = 2T(\frac{n}{2}) + O(n)$，根据主定理，我们可以知道这个解的下界是$O(nlgn)$也就是$\Theta(nlgn)$，但是要比$O(n^2)$要快。

参考内容：

• Leetcode:Maximum Product Subarray
• 算法导论第4章最大值数组问题