Why Maximum Product Subarray in DSA Javascript?

The Big Idea

What if you could find the best stretch of days to multiply your gains without checking every possibility?

The Scenario

Imagine you have a list of numbers representing daily stock price changes. You want to find the best consecutive days to invest to get the highest product of returns.

Doing this by checking every possible group of days manually is like trying to find a needle in a haystack.

The Problem

Manually checking every possible group of days means a lot of repeated work and takes too long as the list grows.

It's easy to make mistakes counting or multiplying wrong, especially with negative numbers and zeros mixed in.

The Solution

The Maximum Product Subarray method quickly finds the best consecutive days by keeping track of the highest and lowest products so far.

This clever approach handles negative numbers and zeros smoothly without checking every group.

Before vs After

✗ Before

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

✓ After

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

What It Enables

This method lets you quickly find the best consecutive segment for maximum product, even with tricky negative numbers and zeros.

Real Life Example

In finance, this helps find the best period to invest when daily returns can be positive or negative, maximizing your overall gain.

Key Takeaways

Manual checking is slow and error-prone for large lists.

Tracking max and min products handles negatives and zeros smartly.

Efficiently finds the maximum product of any consecutive subarray.

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