Maximum Product Subarray
On this page 
Problem Statement Solution 1: Dynamic Programming Approach Solution 2: Prefix Product with Reset Solution 3: Kadane Algorithm Variant Solution 4: Brute Force Approach Solution 5: Sliding Window Approach Solution 6: Maximum Subarray Product with Indices Solution 7: Product Calculation with Zero Reset Solution 8: Prefix Product Calculation with Two Passes Solution 9: Maximum Product Using Logarithms More Problems Solutions
Problem Statement
Given an integer array nums, find a contiguous subarray (containing at least one number) that has the largest product and return the product.
Example 1
Input: array = [1, -2, -3, 4]
Output: 24
Example 2
Input: array = [10, -1, -10, 2, -3, 5]
Output: 300
Solution 1: Dynamic Programming Approach
function maxProduct(nums) {
if (nums.length === 0) return 0;
let maxProduct = nums[0];
let minProduct = nums[0];
let result = nums[0];
for (let i = 1; i < nums.length; i++) {
const num = nums[i];
if (num < 0) {
[maxProduct, minProduct] = [minProduct, maxProduct];
}
maxProduct = Math.max(num, maxProduct * num);
minProduct = Math.min(num, minProduct * num);
result = Math.max(result, maxProduct);
}
return result;
}
const array1 = [1, -2, -3, 4];
maxProduct(array1); //output: 24
const array2 = [10, -1, -10, 2, -3, 5];
maxProduct(array2); //output: 300
Solution 2: Prefix Product with Reset
function maxProductPrefix(nums) {
let maxProduct = nums[0];
let currentProduct = 1;
for (let i = 0; i < nums.length; i++) {
currentProduct *= nums[i];
maxProduct = Math.max(maxProduct, currentProduct);
if (nums[i] === 0) {
currentProduct = 1;
}
}
currentProduct = 1;
for (let i = nums.length - 1; i >= 0; i--) {
currentProduct *= nums[i];
maxProduct = Math.max(maxProduct, currentProduct);
if (nums[i] === 0) {
currentProduct = 1;
}
}
return maxProduct;
}
const array1 = [1, -2, -3, 4];
maxProductPrefix(array1); //output: 24
const array2 = [10, -1, -10, 2, -3, 5];
maxProductPrefix(array2); //output: 300
Solution 3: Kadane Algorithm Variant
function maxProductKadane(nums) {
let maxProduct = nums[0];
let currentMax = nums[0];
let currentMin = nums[0];
for (let i = 1; i < nums.length; i++) {
let tempMax = Math.max(nums[i], currentMax * nums[i], currentMin * nums[i]);
currentMin = Math.min(nums[i], currentMax * nums[i], currentMin * nums[i]);
currentMax = tempMax;
maxProduct = Math.max(maxProduct, currentMax);
}
return maxProduct;
}
const array1 = [1, -2, -3, 4];
maxProductKadane(array1); //output: 24
const array2 = [10, -1, -10, 2, -3, 5];
maxProductKadane(array2); //output: 300
Solution 4: Brute Force Approach
function maxProductBruteForce(nums) {
let maxProduct = -Infinity;
for (let i = 0; i < nums.length; i++) {
let currentProduct = 1;
for (let j = i; j < nums.length; j++) {
currentProduct *= nums[j];
maxProduct = Math.max(maxProduct, currentProduct);
}
}
return maxProduct;
}
const array1 = [1, -2, -3, 4];
maxProductBruteForce(array1); //output: 24
const array2 = [10, -1, -10, 2, -3, 5];
maxProductBruteForce(array2); //output: 300
Solution 5: Sliding Window Approach
function maxProductSlidingWindow(nums) {
let maxProduct = nums[0];
let currentProduct = 1;
for (let i = 0; i < nums.length; i++) {
currentProduct *= nums[i];
maxProduct = Math.max(maxProduct, currentProduct);
if (nums[i] === 0) {
currentProduct = 1;
}
}
currentProduct = 1;
for (let i = nums.length - 1; i >= 0; i--) {
currentProduct *= nums[i];
maxProduct = Math.max(maxProduct, currentProduct);
if (nums[i] === 0) {
currentProduct = 1;
}
}
return maxProduct;
}
const array1 = [1, -2, -3, 4];
maxProductSlidingWindow(array1); //output: 24
const array2 = [10, -1, -10, 2, -3, 5];
maxProductSlidingWindow(array2); //output: 300
Solution 6: Maximum Subarray Product with Indices
function maxProductWithIndices(nums) {
let maxProduct = nums[0];
let curMax = nums[0];
let curMin = nums[0];
let start = 0, end = 0, s = 0;
for (let i = 1; i < nums.length; i++) {
const num = nums[i];
if (num < 0) {
[curMax, curMin] = [curMin, curMax];
}
curMax = Math.max(num, curMax * num);
curMin = Math.min(num, curMin * num);
if (curMax > maxProduct) {
maxProduct = curMax;
start = s;
end = i;
}
if (curMax < 1) {
s = i + 1;
}
}
return maxProduct;
}
const array1 = [1, -2, -3, 4];
maxProductWithIndices(array1); //output: 24
const array2 = [10, -1, -10, 2, -3, 5];
maxProductWithIndices(array2); //output: 300
Solution 7: Product Calculation with Zero Reset
function maxProductZeroReset(nums) {
let maxProduct = nums[0];
let currentProduct = 1;
for (let i = 0; i < nums.length; i++) {
currentProduct *= nums[i];
if (nums[i] === 0) {
currentProduct = 1;
}
maxProduct = Math.max(maxProduct, currentProduct);
}
currentProduct = 1;
for (let i = nums.length - 1; i >= 0; i--) {
currentProduct *= nums[i];
if (nums[i] === 0) {
currentProduct = 1;
}
maxProduct = Math.max(maxProduct, currentProduct);
}
return maxProduct;
}
const array1 = [1, -2, -3, 4];
maxProductZeroReset(array1); //output: 24
const array2 = [10, -1, -10, 2, -3, 5];
maxProductZeroReset(array2); //output: 300
Solution 8: Prefix Product Calculation with Two Passes
function maxProductTwoPass(nums) {
let maxProduct = nums[0];
let prefixProduct = 1;
let suffixProduct = 1;
for (let i = 0; i < nums.length; i++) {
prefixProduct *= nums[i];
suffixProduct *= nums[nums.length - 1 - i];
maxProduct = Math.max(maxProduct, prefixProduct, suffixProduct);
if (prefixProduct === 0) prefixProduct = 1;
if (suffixProduct === 0) suffixProduct = 1;
}
return maxProduct;
}
const array1 = [1, -2, -3, 4];
maxProductTwoPass(array1); //output: 24
const array2 = [10, -1, -10, 2, -3, 5];
maxProductTwoPass(array2); //output: 300
Solution 9: Maximum Product Using Logarithms
function maxProductLogarithms(nums) {
if (nums.length === 0) return 0;
let maxProduct = nums[0];
let curMax = nums[0];
let curMin = nums[0];
for (let i = 1; i < nums.length; i++) {
const num = nums[i];
if (num < 0) {
[curMax, curMin] = [curMin, curMax];
}
curMax = Math.max(num, curMax * num);
curMin = Math.min(num, curMin * num);
maxProduct = Math.max(maxProduct, curMax);
}
return maxProduct;
}
const array1 = [1, -2, -3, 4];
maxProductLogarithms(array1); //output: 24
const array2 = [10, -1, -10, 2, -3, 5];
maxProductLogarithms(array2); //output: 300