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