Leetcode 152. 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.

题目意思就是求一个连续子数组，其乘积最大。

看到这里，二话不说，先暴力求解

public int maxProduct(int[] nums) {
        int maxs=nums[0];
        int[][] DP=new int[nums.length][nums.length];
        for(int i=0;i<nums.length;i++)
            for(int j=i;j<nums.length;j++){
                if(i==j) DP[i][j]=nums[j];
                else  DP[i][j]=DP[i][j-1]*nums[j];
                maxs=Math.max(DP[i][j],maxs);
            }
        
        return maxs;
    }

复杂度为O(n)，然后就。。。。。超时了。

那么研究下题目，不难发现可以动态规划求解，由于是连续的子数组，那么可以设DP[n]为以第n个元素结尾的子数组最大乘积，得到状态方程如下：

DP[n]=max(DP[n-1]*nums[n],nums[n]);

边界为 DP[0]=nums[0]; 然后结果就是求DP[0~n]的最大值了。

其实，到这里题目只解了一半，由于乘积有一种特殊情况----负负得正。比如例子【2,-5,-2】，如果用上面的状态方程，得到的DP数组为【2,-5,10】

显然不对。那么状态方程需要改进为考虑负值的情况，不难发现，只有当负值越大，两负数得到的乘积越大，那么，我们记录MDP[n]为以第n个元素结尾的子数组最小乘积。

DP[n]=max（max(DP[n-1]*nums[n],nums[n])，MDP[n-1]*nums[n]);

MDP[n]=min(min(DP[n-1]*nums[n],nums[n]),MDP[n-1]*nums[n]);

最终代码如下，复杂度为O(n),为了方便大家理解上面用了两个一维数组，实际上每次循环都只用了DP[n-1]和MDP[n-1]的数据，可以优化为用一个变量保存。

public int maxProduct(int[] nums) {
        int maxs=nums[0];
        int[] DP=new int[nums.length];
        int minx=nums[0]; 
        for(int i=0;i<nums.length;i++){
            if(i==0) DP[i]=nums[0];
            else{
                DP[i]=Math.max(Math.max(DP[i-1]*nums[i],nums[i]),minx*nums[i]);
                minx=Math.min(Math.min(DP[i-1]*nums[i],nums[i]),minx*nums[i]);                
            }
            maxs=Math.max(DP[i],maxs);
        }
        return maxs;
    }