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

[分析] 注意到负负得正，所以求解过程中需要分别计算保留以当前数组元素A[i]结尾的连续子数组乘积的最大值和最小值

 

public class Solution {
    // O(N)空间 + O(N)时间
    public int maxProduct1(int[] A) {
        if (A == null || A.length == 0)
            return 0;
        int n = A.length;
        int[] max = new int[n];
        int[] min = new int[n];
        // 初始化条件
        max[0] = A[0];
        min[0] = A[0];
        int finalMax = A[0];
        for (int i = 1; i < n; i++) {
            // 递推式
            max[i] = Math.max(A[i], Math.max(max[i - 1] * A[i], min[i - 1] * A[i]));
            min[i] = Math.min(A[i], Math.min(max[i - 1] * A[i], min[i - 1] * A[i]));
            if (max[i] > finalMax)
                finalMax = max[i];
        }
        return finalMax;
    }
    
    // O(1)空间 + O(N)时间，仅需保留上一步的结果
    public int maxProduct(int[] A) {
        if (A == null || A.length == 0)
            return 0;
        int n = A.length;
        int[] max = new int[2];
        int[] min = new int[2];
        max[0] = A[0];
        min[0] = A[0];
        int finalMax = A[0];
        for (int i = 1; i < n; i++) {
            max[1] = Math.max(A[i], Math.max(max[0] * A[i], min[0] * A[i]));
            min[1] = Math.min(A[i], Math.min(max[0] * A[i], min[0] * A[i]));
            if (max[1] > finalMax)
                finalMax = max[1];
            max[0] = max[1];
            min[0] = min[1];
        }
        return finalMax;
    }
}

 

 

评论

1 楼 qb_2008 2015-04-14  

本以为想到min，max也没什么用，总需要计算O(n^2)的乘积结果，原来计算了min，max之后只要一维DP就行了。如果数很大，需要BigInt计算，那差距就更大了。