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 and minProduct of the same length as nums, initialized to 0.
• Set the first element of both maxProduct and minProduct to the first element of nums.
• Initialize result to the first element of nums.

DP Array Updates:

• Loop through the array starting from the second element.
• For each element nums[i], compute the new values of maxProduct[i] and minProduct[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 and minProduct for each index, update result with the maximum value of maxProduct[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 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;
}

Maximum Product Subarray - LeetCode