# 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!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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.