Maximum Product Subarray in DSA Javascript

Mental Model

We want to find the biggest product of a continuous part of the list. Because multiplying negatives can flip signs, we keep track of both the biggest and smallest products so far.

Analogy: Imagine walking on a path where stepping on some stones doubles your speed and some stones reverse your direction. To find the fastest speed you can get on any stretch, you remember both your fastest and slowest speeds at each step.

Array: [2] -> [-3] -> [4] -> [-1] -> [0] -> [5] -> [-2] -> null
Track maxProd and minProd at each step to handle sign flips.

Dry Run Walkthrough

Input: array: [2, -3, 4, -1, 0, 5, -2]

Goal: Find the maximum product of any continuous subarray

Step 1: Start with maxProd = 2, minProd = 2, result = 2

maxProd=2, minProd=2, result=2

Why: Initialize with first element to start tracking products

Step 2: Process -3: swap maxProd and minProd because -3 is negative; maxProd = max(-3, 2 * -3) = -3; minProd = min(-3, 2 * -3) = -6; update result = max(2, -3) = 2

maxProd=-3, minProd=-6, result=2

Why: Negative flips max and min, so swap to keep track correctly

Step 3: Process 4: maxProd = max(4, -3 * 4) = 4; minProd = min(4, -6 * 4) = -24; update result = max(2, 4) = 4

maxProd=4, minProd=-24, result=4

Why: 4 can start new subarray or extend previous; update max and min

Step 4: Process -1: swap maxProd and minProd; maxProd = max(-1, -24 * -1) = 24; minProd = min(-1, 4 * -1) = -4; update result = max(4, 24) = 24

maxProd=24, minProd=-4, result=24

Why: Negative flips max and min; product grows large

Step 5: Process 0: maxProd = max(0, 24 * 0) = 0; minProd = min(0, -4 * 0) = 0; update result = max(24, 0) = 24

maxProd=0, minProd=0, result=24

Why: Zero resets product; start fresh from next element

Step 6: Process 5: maxProd = max(5, 0 * 5) = 5; minProd = min(5, 0 * 5) = 0; update result = max(24, 5) = 24

maxProd=5, minProd=0, result=24

Why: Start new subarray with 5 or extend zero product

Step 7: Process -2: swap maxProd and minProd; maxProd = max(-2, 0 * -2) = 0; minProd = min(-2, 5 * -2) = -10; update result = max(24, 0) = 24

maxProd=0, minProd=-10, result=24

Why: Negative flips max and min; minProd becomes negative large

Result:

Maximum product subarray = 24 (from subarray [2, -3, 4, -1])

Annotated Code

DSA Javascript

class Solution {
  maxProduct(nums) {
    if (nums.length === 0) return 0;
    let maxProd = nums[0];
    let minProd = nums[0];
    let result = nums[0];
    for (let i = 1; i < nums.length; i++) {
      let curr = nums[i];
      if (curr < 0) {
        // Swap maxProd and minProd because negative flips sign
        [maxProd, minProd] = [minProd, maxProd];
      }
      maxProd = Math.max(curr, maxProd * curr); // max product ending here
      minProd = Math.min(curr, minProd * curr); // min product ending here
      result = Math.max(result, maxProd); // update global max
    }
    return result;
  }
}

// Driver code
const sol = new Solution();
const input = [2, -3, 4, -1, 0, 5, -2];
console.log(sol.maxProduct(input));

if (curr < 0) { [maxProd, minProd] = [minProd, maxProd]; }

swap max and min when current number is negative to handle sign flip

maxProd = Math.max(curr, maxProd * curr);

update max product ending at current position

minProd = Math.min(curr, minProd * curr);

update min product ending at current position

result = Math.max(result, maxProd);

update global maximum product found so far

Output

24

Complexity Analysis

Time: O(n) because we scan the array once, updating max and min products at each step

Space: O(1) because we use only a few variables to track products and result

vs Alternative: Naive approach tries all subarrays with O(n^2) or O(n^3) time; this method is much faster with O(n)

Edge Cases

empty array

returns 0 immediately

DSA Javascript

if (nums.length === 0) return 0;

array with one element

returns that element as max product

DSA Javascript

let maxProd = nums[0];

array with zeros

resets product calculation at zero, starts fresh after zero

DSA Javascript

maxProd = Math.max(curr, maxProd * curr);

When to Use This Pattern

When you need the maximum product of a continuous subarray and negatives can flip signs, use the max/min product tracking pattern to handle sign changes efficiently.

Common Mistakes

Mistake: Not swapping max and min products when encountering a negative number
Fix: Swap maxProd and minProd before updating them when current number is negative

Mistake: Only tracking max product and ignoring min product
Fix: Track both max and min products to handle negative numbers correctly

Summary

Finds the maximum product of any continuous subarray in a list.

Use when the array contains positive, negative, and zero values and you want the largest product subarray.

Keep track of both maximum and minimum products at each step to handle sign flips caused by negatives.

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