Maximum Product Subarray

Problem Statement

Solution 1: Dynamic Programming Approach

function maxProduct(nums) {
    if (nums.length === 0) return 0;

    let maxProduct = nums[0];
    let minProduct = nums[0];
    let result = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];
        
        if (num < 0) {
            [maxProduct, minProduct] = [minProduct, maxProduct];
        }

        maxProduct = Math.max(num, maxProduct * num);
        minProduct = Math.min(num, minProduct * num);

        result = Math.max(result, maxProduct);
    }

    return result;
} 

const array1 = [1, -2, -3, 4];
maxProduct(array1);  //output: 24 

const array2 = [10, -1, -10, 2, -3, 5];
maxProduct(array2);  //output: 300 

Solution 2: Prefix Product with Reset

function maxProductPrefix(nums) {
    let maxProduct = nums[0];
    let currentProduct = 1;

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

        if (nums[i] === 0) {
            currentProduct = 1;
        }
    }

    currentProduct = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        currentProduct *= nums[i];
        maxProduct = Math.max(maxProduct, currentProduct);

        if (nums[i] === 0) {
            currentProduct = 1;
        }
    }

    return maxProduct;
} 

const array1 = [1, -2, -3, 4];
maxProductPrefix(array1);  //output: 24 

const array2 = [10, -1, -10, 2, -3, 5];
maxProductPrefix(array2);  //output: 300 

Solution 3: Kadane Algorithm Variant

function maxProductKadane(nums) {
    let maxProduct = nums[0];
    let currentMax = nums[0];
    let currentMin = nums[0];

    for (let i = 1; i < nums.length; i++) {
        let tempMax = Math.max(nums[i], currentMax * nums[i], currentMin * nums[i]);
        currentMin = Math.min(nums[i], currentMax * nums[i], currentMin * nums[i]);
        currentMax = tempMax;
        maxProduct = Math.max(maxProduct, currentMax);
    }

    return maxProduct;
} 

const array1 = [1, -2, -3, 4];
maxProductKadane(array1);  //output: 24 

const array2 = [10, -1, -10, 2, -3, 5];
maxProductKadane(array2);  //output: 300 

Solution 4: Brute Force Approach

function maxProductBruteForce(nums) {
    let maxProduct = -Infinity;

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

    return maxProduct;
} 

const array1 = [1, -2, -3, 4];
maxProductBruteForce(array1);  //output: 24 

const array2 = [10, -1, -10, 2, -3, 5];
maxProductBruteForce(array2);  //output: 300 

Solution 5: Sliding Window Approach

function maxProductSlidingWindow(nums) {
    let maxProduct = nums[0];
    let currentProduct = 1;

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

    currentProduct = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        currentProduct *= nums[i];
        maxProduct = Math.max(maxProduct, currentProduct);
        if (nums[i] === 0) {
            currentProduct = 1;
        }
    }

    return maxProduct;
} 

const array1 = [1, -2, -3, 4];
maxProductSlidingWindow(array1);  //output: 24 

const array2 = [10, -1, -10, 2, -3, 5];
maxProductSlidingWindow(array2);  //output: 300 

Solution 6: Maximum Subarray Product with Indices

function maxProductWithIndices(nums) {
    let maxProduct = nums[0];
    let curMax = nums[0];
    let curMin = nums[0];
    let start = 0, end = 0, s = 0;

    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];
        if (num < 0) {
            [curMax, curMin] = [curMin, curMax];
        }

        curMax = Math.max(num, curMax * num);
        curMin = Math.min(num, curMin * num);

        if (curMax > maxProduct) {
            maxProduct = curMax;
            start = s;
            end = i;
        }

        if (curMax < 1) {
            s = i + 1;
        }
    }

    return maxProduct;
} 

const array1 = [1, -2, -3, 4];
maxProductWithIndices(array1);  //output: 24 

const array2 = [10, -1, -10, 2, -3, 5];
maxProductWithIndices(array2);  //output: 300 

Solution 7: Product Calculation with Zero Reset

function maxProductZeroReset(nums) {
    let maxProduct = nums[0];
    let currentProduct = 1;

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

    currentProduct = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        currentProduct *= nums[i];
        if (nums[i] === 0) {
            currentProduct = 1;
        }
        maxProduct = Math.max(maxProduct, currentProduct);
    }

    return maxProduct;
} 

const array1 = [1, -2, -3, 4];
maxProductZeroReset(array1);  //output: 24 

const array2 = [10, -1, -10, 2, -3, 5];
maxProductZeroReset(array2);  //output: 300 

Solution 8: Prefix Product Calculation with Two Passes

function maxProductTwoPass(nums) {
    let maxProduct = nums[0];
    let prefixProduct = 1;
    let suffixProduct = 1;

    for (let i = 0; i < nums.length; i++) {
        prefixProduct *= nums[i];
        suffixProduct *= nums[nums.length - 1 - i];
        maxProduct = Math.max(maxProduct, prefixProduct, suffixProduct);
        if (prefixProduct === 0) prefixProduct = 1;
        if (suffixProduct === 0) suffixProduct = 1;
    }

    return maxProduct;
} 

const array1 = [1, -2, -3, 4];
maxProductTwoPass(array1);  //output: 24 

const array2 = [10, -1, -10, 2, -3, 5];
maxProductTwoPass(array2);  //output: 300 

Solution 9: Maximum Product Using Logarithms

function maxProductLogarithms(nums) {
    if (nums.length === 0) return 0;

    let maxProduct = nums[0];
    let curMax = nums[0];
    let curMin = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];
        if (num < 0) {
            [curMax, curMin] = [curMin, curMax];
        }

        curMax = Math.max(num, curMax * num);
        curMin = Math.min(num, curMin * num);

        maxProduct = Math.max(maxProduct, curMax);
    }

    return maxProduct;
} 

const array1 = [1, -2, -3, 4];
maxProductLogarithms(array1);  //output: 24 

const array2 = [10, -1, -10, 2, -3, 5];
maxProductLogarithms(array2);  //output: 300 

More Problems Solutions