--

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

--

--

Sonika | @Walmart | Frontend Developer | 11 Years
Sonika | @Walmart | Frontend Developer | 11 Years

No responses yet