Maximum Product Subarray in DSA Go - Execution Trace

Concept Flow - Maximum Product Subarray

Start at index 0

↓

Initialize max_prod, min_prod, result

↓

For each element i in array

↓

Calculate temp max and min products

↓

Update max_prod and min_prod

↓

Update result if max_prod > result

↓

Move to next element

↓

End of array?

No→Repeat loop

Yes↓

Return result

We move through the array, keeping track of the maximum and minimum products ending at each position, updating the overall maximum product found.

Execution Sample

DSA Go

nums := []int{2, 3, -2, 4}
maxProd, minProd, result := nums[0], nums[0], nums[0]
for i := 1; i < len(nums); i++ {
  tempMax := max(nums[i], maxProd*nums[i], minProd*nums[i])
  tempMin := min(nums[i], maxProd*nums[i], minProd*nums[i])
  maxProd = tempMax
  minProd = tempMin
  if maxProd > result {
    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	Index	Current Number	maxProd	minProd	Result	Visual State (Subarray with max product)
1	Initialize	0	2	2	2	2	[2]
2	Process element	1	3	6	3	6	[2, 3]
3	Process element	2	-2	-2	-12	6	[2, 3]
4	Process element	3	4	-8	-48	6	[2, 3]
5	End	-	-	-	-	6	[2, 3]

💡 Reached end of array, final maximum product is 6 from subarray [2, 3]

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
maxProd	2	6	-2	-8	-8
minProd	2	3	-12	-48	-48
result	2	6	6	6	6

Key Moments - 3 Insights

Why do we track both maxProd and minProd at each step?

Because a negative number can turn a small (negative) minProd into a large positive product, tracking both helps find the maximum product subarray (see steps 3 and 4 in execution_table).

Why does maxProd sometimes become negative after processing an element?

When multiplying by a negative number, the maxProd can become negative if the previous maxProd was positive. But minProd might become large negative, which can flip to maxProd in next steps (see step 3 and 4).

Why is the initial result set to the first element?

Because the maximum product subarray must include at least one element, starting with the first element ensures we have a valid initial maximum (see step 1).

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the value of minProd after processing index 2?

A -2

B -12

C 3

D 6

💡 Hint

Check the 'minProd' column in execution_table row for step 3.

At which step does the result get updated to 6?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'result' column in execution_table and see when it changes from 2 to 6.

If the array started with a negative number instead of 2, how would the initial maxProd and minProd be set?

A Both set to 0

B maxProd set to 0, minProd to negative number

C Both set to that negative number

D maxProd set to negative number, minProd set to 0

💡 Hint

Initial maxProd and minProd are always set to the first element of the array (see variable_tracker start values).

Concept Snapshot

Maximum Product Subarray:
- Track maxProd and minProd at each index
- maxProd = max(current number, maxProd*current, minProd*current)
- minProd = min(current number, maxProd*current, minProd*current)
- Update result with maxProd
- Handles negative numbers by tracking minProd
- Returns max product of any contiguous subarray

Full Transcript

The Maximum Product Subarray problem finds the largest product of any contiguous subarray within an array. We start by setting maxProd, minProd, and result to the first element. Then, for each element, we calculate temporary max and min products considering the current number and previous maxProd and minProd multiplied by it. We update maxProd and minProd accordingly. The result is updated if maxProd is greater. This approach handles negative numbers by tracking minProd, which can become maxProd if multiplied by a negative number. The final result is the maximum product found. The execution table shows step-by-step how maxProd, minProd, and result change as we process each element.

Practice

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

easy

A. The longest subarray with positive numbers

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

C. The maximum single element in the array

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

Solution

1. Step 1: Understand the problem statement

   The problem asks for a contiguous part of the array where the product of all elements is the highest possible.

2. Step 2: Differentiate from similar problems

   Unlike maximum sum subarray, here we multiply elements, so negative numbers and zeros affect the product differently.

3. Final Answer:

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

4. Quick Check:

   Maximum product subarray = contiguous subarray with max product [OK]

Hint: Look for contiguous elements with max multiplication [OK]

Common Mistakes:

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

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

easy

A. maxProd, minProd, result := 1, 1, 1

B. maxProd, minProd, result := 0, 0, 0

C. maxProd, minProd, result := nums[0], nums[0], nums[0]

D. maxProd, minProd, result := -1, -1, -1

Solution

1. Step 1: Understand initialization for max product subarray

   We start with the first element as initial max, min, and result to handle negative and positive values correctly.

2. Step 2: Check each option's initialization

   maxProd, minProd, result := nums[0], nums[0], nums[0] uses nums[0] which is correct; others use fixed values that may not match array's first element.

3. Final Answer:

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

4. Quick Check:

   Initialize with first element for correct tracking [OK]

Hint: Initialize with first element, not zero or one [OK]

Common Mistakes:

• Initializing with zero causes wrong results if nums[0] is negative
• Using 1 ignores negative or zero first elements
• Not initializing minProd separately

3. What is the output of the following Go code for the input array nums := []int{2, 3, -2, 4}?

func maxProduct(nums []int) int {
    maxProd, minProd, result := nums[0], nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] < 0 {
            maxProd, minProd = minProd, maxProd
        }
        maxProd = max(nums[i], maxProd*nums[i])
        minProd = min(nums[i], minProd*nums[i])
        if maxProd > result {
            result = maxProd
        }
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

medium

A. 6

B. 4

C. -2

D. 8

Solution

1. Step 1: Trace the loop and update maxProd, minProd, and result

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

2. Step 2: Determine final result

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

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Max product subarray = 6 [OK]

Hint: Swap max and min when negative number found [OK]

Common Mistakes:

• Not swapping max and min on negative number
• Confusing max and min updates
• Ignoring update of result

4. Identify the bug in this Go code snippet for maximum product subarray:

func maxProduct(nums []int) int {
    maxProd, minProd, result := nums[0], nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] > 0 {
            maxProd = max(maxProd*nums[i], nums[i])
            minProd = min(minProd*nums[i], nums[i])
        } else {
            maxProd = max(minProd*nums[i], nums[i])
            minProd = min(maxProd*nums[i], nums[i])
        }
        if maxProd > result {
            result = maxProd
        }
    }
    return result
}

medium

A. Swapping maxProd and minProd is missing when nums[i] is negative

B. Initialization of maxProd, minProd, result is incorrect

C. Loop should start from i = 0 instead of 1

D. max and min functions are not defined

Solution

1. Step 1: Analyze handling of negative numbers

   When nums[i] is negative, maxProd and minProd should be swapped before updating because multiplying by negative flips max and min.

2. Step 2: Check the code's else block

   The code updates maxProd and minProd without swapping, causing incorrect results for negative numbers.

3. Final Answer:

   Swapping maxProd and minProd is missing when nums[i] is negative -> Option A

4. Quick Check:

   Swap max and min on negative input [OK]

Hint: Always swap max and min before multiplying negative number [OK]

Common Mistakes:

• Forgetting to swap maxProd and minProd
• Updating maxProd before minProd causing wrong minProd
• Starting loop at wrong index

5. Given the array nums := []int{-1, -3, -10, 0, 60}, what is the maximum product subarray and its product?

hard

A. Subarray [-1, -3, -10] with product -30

B. Subarray [60] with product 60

C. Subarray [-3, -10, 0, 60] with product 0

D. Subarray [-10, 0, 60] with product 0

Solution

1. Step 1: Evaluate products of possible subarrays

   Check subarrays: - [-1, -3, -10]: product = -1 * -3 * -10 = -30 - [60]: product = 60 - [-3, -10, 0, 60]: product = 0 (due to zero) - [-10, 0, 60]: product = 0 (due to zero)

2. Step 2: Identify maximum product

   The highest product is 60 from subarray [60].

3. Final Answer:

   Subarray [60] with product 60 -> Option B

4. Quick Check:

   Max product = 60 from single element [OK]

Hint: Check single elements when zeros reset product [OK]

Common Mistakes:

• Multiplying negative numbers without counting sign flips
• Ignoring zero resets product
• Assuming longer subarray always has max product