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 — Time O(N), Space — O(N)
Explanation
Initialization:
- Create two arrays
maxProduct
andminProduct
of the same length asnums
, initialized to 0. - Set the first element of both
maxProduct
andminProduct
to the first element ofnums
. - Initialize
result
to the first element ofnums
.
DP Array Updates:
- Loop through the array starting from the second element.
- For each element
nums[i]
, compute the new values ofmaxProduct[i]
andminProduct[i]
by considering:
The current element nums[i]
.
The product of the current element and the previous maxProduct[i - 1]
.
The product of the current element and the previous minProduct[i - 1]
.
- Update
maxProduct[i]
with the maximum of these three values. - Update
minProduct[i]
with the minimum of these three values.
Update Result:
- After updating
maxProduct
andminProduct
for each index, updateresult
with the maximum value ofmaxProduct[i]
.
Final Result:
- The
result
variable will contain the maximum product of any subarray.
function maxProduct(nums) {
const n = nums.length;
if (n === 0) return 0;
// Initialize the dp arrays
let maxProduct = Array(n).fill(0);
let minProduct = Array(n).fill(0);
// Initial values
maxProduct[0] = nums[0];
minProduct[0] = nums[0];
let result = nums[0];
// Fill the dp arrays
for (let i = 1; i < n; i++) {
maxProduct[i] = Math.max(nums[i], nums[i] * maxProduct[i - 1], nums[i] * minProduct[i - 1]);
minProduct[i] = Math.min(nums[i], nums[i] * maxProduct[i - 1], nums[i] * minProduct[i - 1]);
// Update the result with the maximum product found so far
result = Math.max(result, maxProduct[i]);
}
return result;
}
// Example usage:
const nums = [2, 3, -2, 4];
console.log(maxProduct(nums)); // Output: 6
Optimsed -
This optimized version achieves the same result with O(1)O(1)O(1) space complexity by reusing variables instead of arrays.
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
andminProduct
) 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;
}