Find the Contiguous Subarray with the Largest Product in a given Array of Integers using JavaScript - Coding

The objective is to find a contiguous subarray (one in which the elements are adjacent) with the largest product of its elements given an integer array. There are several approaches to finding the contiguous subarray with the largest products using JavaScript which are as follows:

Table of Content

Brute Force Approach
Dynamic Programming Approach

Brute Force Approach

In the brute force method, every possible contiguous subarray is checked out and its product is computed. We compute the product of each subarray after iterating through each element in the array and taking note of all subarrays that begin with that element. In the end, we give back the highest product among all subarrays.

Example: Finding the contiguous subarray with the largest product in an array of integers using the brute force approach in JavaScript.

JavaScript

function maxProductBruteForce(nums) {
    let maxProduct = Number.NEGATIVE_INFINITY;
    let start = 0;
    let end = 0;

    for (let i = 0; i < nums.length; i++) {
        let product = 1;
        for (let j = i; j < nums.length; j++) {
            product *= nums[j];
            if (product > maxProduct) {
                maxProduct = product;
                start = i;
                end = j;
            }
        }
    }

    return {
        maxProduct: maxProduct,
        subarray: nums.slice(start, end + 1)
    };
}

// Example Usage
const nums = [2, 3, -2, 4];
const resultBruteForce = 
    maxProductBruteForce(nums);
console.log(
    "Maximum Product (Brute Force):", 
        resultBruteForce.maxProduct);
console.log(
    "Subarray with Maximum Product (Brute Force):", 
        resultBruteForce.subarray);

Output

Maximum Product (Brute Force): 6
Subarray with Maximum Product (Brute Force): [ 2, 3 ]

Time Complexity: O(n^2)

Space Complexity: O(1)

Dynamic Programming Approach

The dynamic programming approach tracks `maxProduct` and `minProduct` at each element, updating them with the current element to handle negative numbers and find the largest product subarray. `maxProduct` holds the maximum product ending at the current index, while `minProduct` holds the minimum.

Example: Given an array of integers, find the contiguous subarray with the largest product using an optimized dynamic programming approach in JavaScript.

JavaScript

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

    let maxProduct = nums[0];
    let minProduct = nums[0];
    let result = nums[0];
    let start = 0;
    let end = 0;
    let tempStart = 0;

    for (let i = 1; i < nums.length; i++) {
        // Calculate new max and min products
        let tempMax = maxProduct;
        maxProduct = Math.max(nums[i],
                     nums[i] * maxProduct,
                     nums[i] * minProduct);
        minProduct = Math
        .min(nums[i],
             nums[i] * tempMax, nums[i] * minProduct);
        
        // Update result if 
        // maxProduct is greater
        if (maxProduct > result) {
            result = maxProduct;
            start = tempStart;
            end = i;
        }

        // If current number is 0, reset 
        // start position for next subarray
        if (nums[i] === 0) {
            tempStart = i + 1;
        }
    }

    return {
        maxProduct: result,
        subarray: nums
        .slice(start, end + 1)
    };
}


const nums = [2, 3, -2, 4];
const resultDynamic = 
    maxProductDynamic(nums);
console.log(
    "Maximum Product (Dynamic Programming):", 
        resultDynamic.maxProduct);
console.log(
    "Subarray with Maximum Product (Dynamic Programming):", 
        resultDynamic.subarray);

Output

Maximum Product (Dynamic Programming): 6
Subarray with Maximum Product (Dynamic Programming): [ 2, 3 ]

Time Complexity: O(n)

Space Complexity: O(1)

Reffered: https://www.geeksforgeeks.org

JavaScript

Related
Convert 2D Array to Object using Map or Reduce in JavaScript
How to Import Lodash Libraries in JavaScript ?
JavaScript Program to Remove Loop in a Linked List
How to Post JSON Data using Curl ?
Design a Decimal to Binary Converter in VueJS

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	14