Maximum Product Subarray | 1D | Dynamic Programming

I’m excited to help you out, Let’s Connect!
👏
Please clap for the story and follow me 👉

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Brute Force (Two Nested Loops)

Time complexity of O(n²)

function maxProduct(nums) {
const n = nums.length;
let maxProduct = Number.MIN_SAFE_INTEGER;

for (let i = 0; i < n; i++) {
let currentProduct = 1;
for (let j = i; j < n; j++) {
currentProduct *= nums[j];
maxProduct = Math.max(maxProduct, currentProduct);
}
}

return maxProduct;
}

// Example usage
const nums = [2, 3, -2, 4];
console.log(maxProduct(nums)); // Output: 6

Dynamic Programming — O(N)

HINT —

If we get all positive number, then we will be increasing the index and move forward with maxProduct — Product is increasing

If we get all negative number, then we will be increasing the index and move forward with minProduct — Product is decreasing

Why SWAP maxProduct and minProduct ??

  • It’s swaping the values of two variables (maxProduct and minProduct) in a single line
  • This line is used to handle negative numbers.
  • Since multiplying a negative number by a negative number results in a positive number, we need to keep track of both the maximum and minimum products when encountering negative numbers.
  • The destructuring assignment helps in swapping these values effectively.
[maxProduct, minProduct] = [minProduct, maxProduct];

Implementation,

function maxProduct(nums) {
const n = nums.length;
let maxProduct = nums[0];
let minProduct = nums[0];
let result = nums[0];

for (let i = 1; i < n; i++) {
// Update max and min products considering the current number
if (nums[i] < 0) {
// This line is used to handle negative numbers.
[maxProduct, minProduct] = [minProduct, maxProduct];
}
maxProduct = Math.max(nums[i], maxProduct * nums[i]);
minProduct = Math.min(nums[i], minProduct * nums[i]);

// Update the overall result with the maximum product so far
result = Math.max(result, maxProduct);
}

return result;
}

// Example usage
const nums = [2, 3, -2, 4];
console.log(maxProduct(nums)); // Output: 6

Another Implementation,

/**
* Brute Force - Linear Search
* Time O(N^2) | Space O(1)
* https://leetcode.com/problems/maximum-product-subarray/
* @param {number[]} nums
* @return {number}
*/
var maxProduct = (nums) => {
const isEmpty = nums.length === 0;
if (isEmpty) return 0;

return linearSearch(nums);/* Time O(N * N) */
}

const linearSearch = (nums, max = nums[0]) => {
for (let index = 0; index < nums.length; index++) {/* Time O(N) */
max = getMax(nums, index, max); /* Time O(N) */
}

return max;
}

const getMax = (nums, index, max, product = 1) => {
for (let num = index; num < nums.length; num++) {/* Time O(N) */
product *= nums[num];
max = Math.max(max, product);
}

return max;
}

/**
* Greedy - product
* Time O(N) | Space O(1)
* https://leetcode.com/problems/maximum-product-subarray/
* @param {number[]} nums
* @return {number}
*/
var maxProduct = (nums) => {
const isEmpty = nums.length === 0;
if (isEmpty) return 0;

return greedySearch(nums);/* Time O(N) */
};

const greedySearch = (nums) => {
let min = max = product = nums[0];

for (let num = 1; num < nums.length; num++) {/* Time O(N) */
const [ minProduct, maxProduct ] = [ (min * nums[num]), (max * nums[num]) ];

min = Math.min(maxProduct, minProduct, nums[num]);
max = Math.max(maxProduct, minProduct, nums[num]);

product = Math.max(product, max);
}

return product;
}