Maximum Product Subarray in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Product Subarray Calculation

What is the output of the following Go code that finds the maximum product of a contiguous subarray?

DSA Go

package main
import "fmt"
func maxProduct(nums []int) int {
    maxProd := nums[0]
    minProd := nums[0]
    result := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] < 0 {
            maxProd, minProd = minProd, maxProd
        }
        if nums[i] > maxProd*nums[i] {
            maxProd = nums[i]
        } else {
            maxProd = maxProd * nums[i]
        }
        if nums[i] < minProd*nums[i] {
            minProd = nums[i]
        } else {
            minProd = minProd * nums[i]
        }
        if maxProd > result {
            result = maxProd
        }
    }
    return result
}
func main() {
    nums := []int{2, 3, -2, 4}
    fmt.Println(maxProduct(nums))
}

A 4

B 6

C -2

D 8

💡 Hint

Track max and min products at each step because negative numbers can flip signs.

The maximum product subarray is [2, 3] with product 6. The code tracks max and min products to handle negatives correctly.

❓ Predict Output

intermediate

Result of Maximum Product Subarray with Negative Numbers

What will be printed by this Go program that calculates the maximum product subarray?

DSA Go

package main
import "fmt"
func maxProduct(nums []int) int {
    maxProd := nums[0]
    minProd := nums[0]
    result := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] < 0 {
            maxProd, minProd = minProd, maxProd
        }
        if nums[i] > maxProd*nums[i] {
            maxProd = nums[i]
        } else {
            maxProd = maxProd * nums[i]
        }
        if nums[i] < minProd*nums[i] {
            minProd = nums[i]
        } else {
            minProd = minProd * nums[i]
        }
        if maxProd > result {
            result = maxProd
        }
    }
    return result
}
func main() {
    nums := []int{-2, 0, -1}
    fmt.Println(maxProduct(nums))
}

A 0

B -1

C -2

D 2

💡 Hint

Zero resets the product, so consider subarrays around zero.

The maximum product subarray is [0] with product 0. Negative numbers and zero reset the product tracking.

🔧 Debug

advanced

Identify the Runtime Error in Maximum Product Subarray Code

Which option will cause a runtime error when running the maximum product subarray function in Go?

DSA Go

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

A for i := 1; i <= len(nums); i++ { ... } // causes index out of range

B for i := 1; i < len(nums); i++ { ... } // correct loop

C for i := 0; i < len(nums); i++ { ... } // off by one but no error

D for i := 1; i < len(nums)-1; i++ { ... } // misses last element

💡 Hint

Check loop boundary conditions carefully.

Using i <= len(nums) causes an index out of range error because valid indices are 0 to len(nums)-1.

🧠 Conceptual

advanced

Why Track Both Max and Min Products in Maximum Product Subarray?

Why does the maximum product subarray algorithm track both maximum and minimum products at each step?

A Because minimum product helps to find the longest subarray

B Because minimum product is needed to calculate the sum of subarrays

C Because maximum product alone cannot handle zeros in the array

D Because a negative number can turn a minimum product into a maximum product when multiplied

💡 Hint

Think about how multiplying by a negative number changes signs.

Multiplying by a negative number flips signs, so the minimum product can become the maximum product and vice versa.

🚀 Application

expert

Maximum Product Subarray Length with Maximum Product

Given the array [1, -2, -3, 0, 7, -8, -2], what is the length of the contiguous subarray that produces the maximum product?

A 4

B 2

C 3

D 1

💡 Hint

Find the subarray with the maximum product and count its length.

The maximum product is 112 from subarray [7, -8, -2], which has length 3.

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