Maximum Product Subarray in DSA Javascript - Execution Trace

Concept Flow - Maximum Product Subarray

Start at index 0

↓

Initialize maxProd, minProd, result

↓

For each element from index 1 to end

↓

If element < 0, swap maxProd and minProd

↓

Update maxProd = max(element, maxProd * element)

↓

Update minProd = min(element, minProd * element)

↓

Update result = max(result, maxProd)

↓

Repeat until end

↓

Return result

We move through the array, tracking the maximum and minimum products ending at each position, swapping when negative numbers appear, and keep the highest product found.

Execution Sample

DSA Javascript

const 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;
};

This code finds the maximum product of any contiguous subarray by tracking max and min products at each step.

Execution Table

Step	Operation	Current Element	maxProd Before	minProd Before	Swap? (if negative)	maxProd After	minProd After	Result	Visual State (maxProd, minProd, result)
0	Initialize	nums[0] = 2	-	-	No	2	2	2	(2, 2, 2)
1	Process nums[1]	-5	2	2	Yes (swap)	-5	-10	2	(-5, -10, 2)
2	Process nums[2]	-2	-5	-10	Yes (swap)	20	-2	20	(20, -2, 20)
3	Process nums[3]	4	20	-2	No	80	-8	80	(80, -8, 80)
4	Process nums[4]	3	80	-8	No	240	-24	240	(240, -24, 240)
5	Process nums[5]	-1	240	-24	Yes (swap)	24	-240	240	(24, -240, 240)
6	Process nums[6]	0	24	-240	No	0	0	240	(0, 0, 240)
7	Process nums[7]	1	0	0	No	1	0	240	(1, 0, 240)
8	Process nums[8]	-2	1	0	Yes (swap)	0	-2	240	(0, -2, 240)
9	Process nums[9]	4	0	-2	No	4	-8	240	(4, -8, 240)
Exit	End of array	-	-	-	-	-	-	240	Final max product is 240

💡 Reached end of array, final result is 240

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	Final
maxProd	2	-5	20	80	240	24	0	1	0	4	4
minProd	2	-10	-2	-8	-24	-240	0	0	-2	-8	-8
result	2	2	20	80	240	240	240	240	240	240	240

Key Moments - 3 Insights

Why do we swap maxProd and minProd when the current element is negative?

Because multiplying by a negative flips signs, the max product could become min and min could become max. Swapping ensures correct tracking, as shown in steps 1, 2, 5, and 8 in the execution_table.

Why do we track both maxProd and minProd instead of just maxProd?

Because a minimum product (negative) can become maximum if multiplied by a negative number later. Tracking both lets us handle this, as seen in step 2 where minProd helps get a bigger maxProd.

Why do we compare the current element alone with maxProd * element when updating maxProd?

Because starting fresh from the current element might yield a bigger product than continuing the previous subarray. This is why maxProd = max(nums[i], maxProd * nums[i]) is used, visible in all steps updating maxProd.

Visual Quiz - 3 Questions

Look at the execution_table at step 2. What is the maxProd after processing element -2?

A 2

B 20

C -10

D -5

💡 Hint

Check the 'maxProd After' column at step 2 in execution_table.

At which step does the result first become 240?

A Step 4

B Step 5

C Step 3

D Step 6

💡 Hint

Look at the 'Result' column in execution_table and find when it first reaches 240.

If the element at step 5 was positive instead of -1, what would happen to maxProd and minProd?

A They would swap as usual

B They would not swap and maxProd would increase

C They would not swap and maxProd would decrease

D They would swap and minProd would increase

💡 Hint

Recall swapping happens only if current element is negative, see 'Swap?' column in execution_table.

Concept Snapshot

Maximum Product Subarray:
- Track maxProd and minProd at each index
- Swap maxProd and minProd if current element < 0
- Update maxProd = max(current element, maxProd * current element)
- Update minProd = min(current element, minProd * current element)
- Keep result as max of all maxProd values
- Return result at end

Full Transcript

The Maximum Product Subarray problem is solved by moving through the array and keeping track of two values at each step: the maximum product ending at the current position and the minimum product ending at the current position. We track the minimum because multiplying two negative numbers can produce a positive product. When the current element is negative, we swap the max and min products to correctly update them. At each step, we update maxProd and minProd by comparing the current element alone and the product of the current element with the previous maxProd or minProd. We keep track of the highest maxProd found so far as the result. After processing all elements, the result is the maximum product of any contiguous 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