Maximum Product Subarray in DSA Javascript - Build from Scratch

Maximum Product Subarray

📖 Scenario: You are working on a financial app that analyzes daily stock price changes represented as an array of integers. You want to find the maximum product of a contiguous subarray to understand the best possible gain or loss multiplier over consecutive days.

🎯 Goal: Build a program that finds the maximum product of any contiguous subarray within a given array of integers.

📋 What You'll Learn

Create an array called nums with the exact values [2, 3, -2, 4].

Create two variables called maxProd and minProd and set both to the first element of nums.

Use a for loop with variable i starting from 1 to iterate over nums.

Inside the loop, update maxProd and minProd to track the maximum and minimum products ending at the current index.

Create a variable called result and set it to the first element of nums.

Update result inside the loop to keep track of the maximum product found so far.

Print the value of result.

💡 Why This Matters

🌍 Real World

Finding the maximum product subarray helps in financial analysis to detect the best consecutive days for investment gains or losses.

💼 Career

This problem is common in technical interviews and helps demonstrate understanding of dynamic programming and array manipulation.

1

Create the array of numbers

Create an array called nums with the exact values [2, 3, -2, 4].

DSA Javascript

# Create the array nums with values [2, 3, -2, 4]
// Your code here

Hint

Use const nums = [2, 3, -2, 4]; to create the array.

2

Initialize maxProd and minProd

Create two variables called maxProd and minProd and set both to the first element of nums.

DSA Javascript

const nums = [2, 3, -2, 4];
// Initialize maxProd and minProd to nums[0]
// Your code here

Hint

Use let maxProd = nums[0]; and let minProd = nums[0];.

3

Iterate and update maxProd and minProd

Use a for loop with variable i starting from 1 to iterate over nums. Inside the loop, create a variable tempMax to store the current maxProd. Update maxProd to the maximum of nums[i], maxProd * nums[i], and minProd * nums[i]. Update minProd to the minimum of nums[i], tempMax * nums[i], and minProd * nums[i]. Also, create a variable called result and set it to the first element of nums. Update result inside the loop to keep track of the maximum product found so far.

DSA Javascript

const nums = [2, 3, -2, 4];
let maxProd = nums[0];
let minProd = nums[0];
// Create result and set to nums[0]
// Use for loop from i = 1 to nums.length
// Update maxProd, minProd, and result inside the loop
// Your code here

Hint

Use Math.max and Math.min to update maxProd and minProd. Remember to save the old maxProd in tempMax before updating.

4

Print the maximum product

Print the value of result.

DSA Javascript

const nums = [2, 3, -2, 4];
let maxProd = nums[0];
let minProd = nums[0];
let result = nums[0];
for (let i = 1; i  result) {
        result = maxProd;
    }
}
// Print the result
// Your code here

Hint

Use console.log(result); to print the maximum product.

Practice

1. What does the Maximum Product Subarray problem ask you to find in an array of integers?

easy

A. The subarray with the largest difference between elements

B. The contiguous subarray with the largest sum of its elements

C. The subarray with the smallest product of its elements

D. The contiguous subarray with the largest product of its elements

Solution

1. Step 1: Understand the problem goal

   The problem asks for the contiguous subarray (elements next to each other) that has the maximum product when multiplied together.

2. Step 2: Differentiate from sum problems

   This is different from maximum sum subarray problems because it focuses on multiplication, which can be affected by negative numbers and zeros.

3. Final Answer:

   The contiguous subarray with the largest product of its elements -> Option D

4. Quick Check:

   Maximum Product Subarray = largest product subarray [OK]

Hint: Look for the subarray with the highest multiplication result [OK]

Common Mistakes:

• Confusing product with sum
• Ignoring negative numbers impact
• Thinking about non-contiguous subarrays

2. Which of the following JavaScript code snippets correctly initializes variables to track the maximum product subarray?

easy

A. let maxProd = Infinity, minProd = -Infinity, result = 0;

B. let maxProd = 0, minProd = 0, result = 0;

C. let maxProd = nums[0], minProd = nums[0], result = nums[0];

D. let maxProd = [], minProd = [], result = [];

Solution

1. Step 1: Understand variable roles

   maxProd and minProd track the max and min products ending at current index; result stores the overall max product.

2. Step 2: Correct initialization

   Initializing all three to the first element of the array ensures correct comparison and handling of negative numbers.

3. Final Answer:

   let maxProd = nums[0], minProd = nums[0], result = nums[0]; -> Option C

4. Quick Check:

   Initialize with first element for correct tracking [OK]

Hint: Start tracking with first element, not zero or arrays [OK]

Common Mistakes:

• Initializing with zero causes wrong results if first element is negative
• Using arrays instead of numbers for tracking
• Using Infinity values incorrectly

3. What will be the output of the following JavaScript code?

const nums = [2, 3, -2, 4];
function maxProduct(nums) {
  let maxProd = nums[0], minProd = nums[0], result = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < 0) [maxProd, minProd] = [minProd, maxProd];
    maxProd = Math.max(nums[i], maxProd * nums[i]);
    minProd = Math.min(nums[i], minProd * nums[i]);
    result = Math.max(result, maxProd);
  }
  return result;
}
console.log(maxProduct(nums));

medium

A. 4

B. 6

C. -2

D. 8

Solution

1. Step 1: Trace the loop and variable updates

   Start with maxProd=2, minProd=2, result=2.
   i=1 (3): maxProd=max(3,2*3)=6, minProd=min(3,2*3)=3, result=max(2,6)=6.
   i=2 (-2): nums[i]<0 so swap maxProd and minProd: maxProd=3, minProd=6.
   maxProd=max(-2,3*(-2))=max(-2,-6)=-2, minProd=min(-2,6*(-2))=min(-2,-12)=-12, result=max(6,-2)=6.
   i=3 (4): maxProd=max(4,-2*4)=4, minProd=min(4,-12*4)=-48, result=max(6,4)=6.

2. Step 2: Determine final result

   The maximum product found is 6 from subarray [2,3].

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Max product subarray = 6 [OK]

Hint: Swap max and min when negative to track products correctly [OK]

Common Mistakes:

• Not swapping max and min on negative numbers
• Confusing max product with sum
• Incorrectly updating result

4. Identify the bug in the following code for Maximum Product Subarray and select the fix:

function maxProduct(nums) {
  let maxProd = 0, minProd = 0, result = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] < 0) [maxProd, minProd] = [minProd, maxProd];
    maxProd = Math.max(nums[i], maxProd * nums[i]);
    minProd = Math.min(nums[i], minProd * nums[i]);
    result = Math.max(result, maxProd);
  }
  return result;
}

medium

A. Initialize maxProd, minProd, and result with nums[0] instead of 0

B. Remove the swap of maxProd and minProd when nums[i] < 0

C. Start loop from i = 1 instead of 0

D. Use Math.min instead of Math.max for result update

Solution

1. Step 1: Check variable initialization

   Initializing maxProd, minProd, and result to 0 causes wrong results if nums[0] is negative or non-zero. They should start at nums[0].

2. Step 2: Confirm loop start and swap logic

   Loop starting at 0 is okay if initialization is correct. Swap on negative is needed to handle sign changes.

3. Final Answer:

   Initialize maxProd, minProd, and result with nums[0] instead of 0 -> Option A

4. Quick Check:

   Correct initialization fixes wrong product tracking [OK]

Hint: Always initialize tracking vars with first array element [OK]

Common Mistakes:

• Starting loop at 0 with zero initialization
• Removing swap logic on negative numbers
• Updating result with min instead of max

5. Given the array nums = [1, -2, -3, 0, 7, -8, -2], what is the maximum product of any contiguous subarray?

hard

A. 112

B. 48

C. 7

D. 0

Solution

1. Step 1: Trace subarrays and products

   Check subarrays:
   - [1] = 1
   - [1,-2] = -2
   - [1,-2,-3] = 6
   - [-2,-3] = 6
   - [7] = 7
   - [7,-8] = -56
   - [7,-8,-2] = 112 (max so far)
   Zero resets product.
   Other subarrays have smaller products.

2. Step 2: Identify max product

   The maximum product is 112 from subarray [7, -8, -2].

3. Final Answer:

   112 -> Option A

4. Quick Check:

   Max product subarray = 112 [OK]

Hint: Consider negative pairs and zeros to find max product [OK]

Common Mistakes:

• Ignoring zeros resetting product
• Not considering negative number pairs
• Only checking positive subarrays