LeetCode Maximum Product Subarray: DP and Constant Space

Overview

DP with constant space cost solution is given to solve the LeetCode Maximum Product Subarray problem, difference between Maximum Sum Subarray is discussed too.

Problem Definition

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.

DP Analysis

There is a quite similar one to the previous old problem Maximum Subarray which I discussed in my old post: LeetCode Maximum Subarray: 4 methods, DP, Divide and Conquer. A tempting incorrect DP formula you might want try first is the same but replace the sum with product. That is:
Let P[j] denote the maximum subarray product ended at A[j], the you probably would say P[j] = max(A[j], A[j] * P[j - 1]). This is correct for the sum problem, because negative values and positive values keep the same rule consistently. However, for the product case, it is incorrect, think about this case [2, 3, -2, -4]. The correct solution would involve both the minimum (maximum negative) and maximum value maxs[j] and mins[j], so the dp formula for both of them are

  • maxs[j] = max{A[j], A[j] * maxs[j - 1], A[j] * mins[j - 1]};
  • mins[j] = min{A[j], A[j] * maxs[j - 1], A[j] * mins[j - 1]};

The following is the source code accepted by the LeetCode OJ, note the memory cost is constant!

int maxProduct(int A[], int n) {
    int lower, upper;
    int maxProduct = A[0];
    lower = upper = A[0];

    int tmp1 = 0, tmp2 = 0;
    for (int i =1; i < n; ++i) {
        tmp1 = A[i] * upper;
        tmp2 = A[i] * lower;
        upper = max(max(A[i], tmp1), tmp2);
        lower = min(min(A[i], tmp1), tmp2);
        maxProduct = max(maxProduct, upper);
    }
    return maxProduct;
}

Summary

I discussed the DP solution to solve the LeetCode Maximum Product Subarray problem with constant space cost, as well as difference between Maximum Sum Subarray.

Written on November 11, 2014