ā† Back to DevBytes
Go August 06, 2026 8 min read

Solving Maximum Product Subarray in Go: Step-by-Step Guide

Introduction to Maximum Product Subarray

The Maximum Product Subarray problem is a classic dynamic programming challenge that frequently appears in coding interviews and competitive programming. Given an integer array, the task is to find the contiguous subarray that yields the largest product of its elements. While it sounds similar to the Maximum Subarray Sum problem (Kadane's algorithm), the product variant introduces a unique twist: negative numbers can flip signs, and zeros reset the product entirely.

What Is the Maximum Product Subarray?

Formally, given an array nums of integers (which may contain positive, negative, and zero values), you must return the maximum product of any contiguous subarray within nums. A subarray is a contiguous slice of the array, meaning all elements must be adjacent.

For example, given nums = [2, 3, -2, 4], the subarray [2, 3] produces the maximum product of 6. Even though [2, 3, -2, 4] is longer, its product is -48, which is much smaller.

Why This Problem Matters

This problem is more than an academic exercise. It tests several critical developer skills:

In real-world applications, similar logic appears in financial analysis (maximizing returns over a period), signal processing, and any domain where cumulative multiplicative effects matter.

Understanding the Core Challenge

The tricky part of this problem is that multiplying two negative numbers produces a positive result. This means a very small (very negative) running product can suddenly become the largest product when multiplied by another negative number. Therefore, you cannot simply track the maximum product seen so far ā€” you must also track the minimum product, because the minimum might become the maximum after a sign flip.

Additionally, encountering a zero resets the product chain. Any subarray containing a zero has a product of zero, so you effectively restart your computation after each zero.

Breaking Down the Logic

At each index i, you maintain two values:

When you encounter nums[i], the new currentMax is the largest of:

You compute currentMin symmetrically using the minimum of those three candidates. The global answer is the maximum currentMax observed across all indices.

Step-by-Step Solution in Go

Let's build the solution incrementally. First, here is a straightforward implementation that captures the core algorithm:

package main

import "fmt"

func maxProduct(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    // Initialize with the first element
    currentMax := nums[0]
    currentMin := nums[0]
    result := nums[0]

    for i := 1; i < len(nums); i++ {
        num := nums[i]

        // Store previous values because both updates depend on them
        prevMax := currentMax
        prevMin := currentMin

        if num > num*prevMax && num > num*prevMin {
            currentMax = num
        } else if num*prevMax > num*prevMin {
            currentMax = num * prevMax
        } else {
            currentMax = num * prevMin
        }

        if num < num*prevMin && num < num*prevMax {
            currentMin = num
        } else if num*prevMin < num*prevMax {
            currentMin = num * prevMin
        } else {
            currentMin = num * prevMax
        }

        if currentMax > result {
            result = currentMax
        }
    }

    return result
}

func main() {
    fmt.Println(maxProduct([]int{2, 3, -2, 4}))       // Output: 6
    fmt.Println(maxProduct([]int{-2, 0, -1}))          // Output: 0
    fmt.Println(maxProduct([]int{-2, 3, -4}))          // Output: 24
    fmt.Println(maxProduct([]int{0, 2}))               // Output: 2
    fmt.Println(maxProduct([]int{-2}))                 // Output: -2
}

This works, but the conditional logic is verbose. Go does not have a built-in max function for integers prior to Go 1.21, so we can either define helper functions or use the generics-based max introduced in Go 1.21. Let's refactor for clarity:

Cleaner Implementation with Helper Functions

package main

import "fmt"

func maxOf(a, b, c int) int {
    m := a
    if b > m {
        m = b
    }
    if c > m {
        m = c
    }
    return m
}

func minOf(a, b, c int) int {
    m := a
    if b < m {
        m = b
    }
    if c < m {
        m = c
    }
    return m
}

func maxProduct(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    currentMax := nums[0]
    currentMin := nums[0]
    result := nums[0]

    for i := 1; i < len(nums); i++ {
        num := nums[i]
        prevMax := currentMax
        prevMin := currentMin

        currentMax = maxOf(num, num*prevMax, num*prevMin)
        currentMin = minOf(num, num*prevMax, num*prevMin)

        if currentMax > result {
            result = currentMax
        }
    }

    return result
}

func main() {
    tests := [][]int{
        {2, 3, -2, 4},
        {-2, 0, -1},
        {-2, 3, -4},
        {0, 2},
        {-2},
        {-1, -2, -9, -6},
        {1, 2, 3, 4, 5},
    }
    for _, t := range tests {
        fmt.Printf("maxProduct(%v) = %d\n", t, maxProduct(t))
    }
}

Tracing Through an Example

To solidify understanding, let's trace nums = [-2, 3, -4] step by step:

The final answer is 24, which corresponds to the entire array [-2, 3, -4] since -2 * 3 * -4 = 24. Notice how the negative minimum at index 1 (-6) became crucial for producing the maximum at index 2.

Alternative Approach: Two-Pass Scan

There is an elegant alternative that avoids tracking both min and max explicitly. The idea is to scan the array left to right accumulating a product, resetting to 1 whenever you hit a zero. Then scan right to left doing the same. The maximum value encountered during both passes is the answer. This works because the maximum product subarray either starts from the left side or the right side, and any negative numbers that do not cancel out will be handled by the opposite-direction pass.

package main

import "fmt"

func maxProductTwoPass(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    result := nums[0]
    product := 1

    // Left to right pass
    for i := 0; i < len(nums); i++ {
        product *= nums[i]
        if product > result {
            result = product
        }
        if nums[i] == 0 {
            product = 1
        }
    }

    product = 1
    // Right to left pass
    for i := len(nums) - 1; i >= 0; i-- {
        product *= nums[i]
        if product > result {
            result = product
        }
        if nums[i] == 0 {
            product = 1
        }
    }

    return result
}

func main() {
    fmt.Println(maxProductTwoPass([]int{2, 3, -2, 4}))  // Output: 6
    fmt.Println(maxProductTwoPass([]int{-2, 3, -4}))    // Output: 24
    fmt.Println(maxProductTwoPass([]int{-2, 0, -1}))    // Output: 0
}

This approach is intuitive and concise, but it requires two passes and careful handling of the reset logic. Both approaches run in O(n) time and O(1) space, so the choice often comes down to personal preference and readability.

Best Practices

Table-Driven Test Example

package main

import "testing"

func TestMaxProduct(t *testing.T) {
    tests := []struct {
        name     string
        nums     []int
        expected int
    }{
        {"mixed signs", []int{2, 3, -2, 4}, 6},
        {"with zero", []int{-2, 0, -1}, 0},
        {"two negatives", []int{-2, 3, -4}, 24},
        {"single positive", []int{5}, 5},
        {"single negative", []int{-2}, -2},
        {"all negatives odd count", []int{-1, -2, -3}, 6},
        {"all negatives even count", []int{-1, -2, -3, -4}, 24},
        {"zeros only", []int{0, 0, 0}, 0},
        {"empty array", []int{}, 0},
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            got := maxProduct(tt.nums)
            if got != tt.expected {
                t.Errorf("maxProduct(%v) = %d, want %d", tt.nums, got, tt.expected)
            }
        })
    }
}

Complexity Analysis

Both the dynamic programming approach and the two-pass approach achieve the following complexity:

This is a significant improvement over the naive O(nĀ²) brute-force approach, which would enumerate every possible subarray and compute its product. For large inputs, the difference is substantial.

Conclusion

The Maximum Product Subarray problem is a deceptively simple challenge that rewards careful thinking about state, sign flips, and edge cases. By tracking both the running maximum and minimum products at each position, you can solve the problem in a single pass with constant space. Alternatively, the two-pass scanning approach offers an elegant solution that leverages the symmetry of multiplication. Whichever method you choose, mastering this problem strengthens your dynamic programming instincts and prepares you for a wide range of array manipulation challenges in Go and beyond. Practice with diverse test cases, write clean and well-documented code, and you will be well-equipped to handle this problem confidently in any technical interview or production scenario.

šŸ›  Tools from DevBytes

Inventory Tracker Pro ā€” Excel inventory system, low-stock alerts Ā· $19
AI Dev Kit for Mac ā€” local AI dev environment templates Ā· $9.99
KeyMapper for Mac ā€” custom keyboard shortcut toolkit Ā· $7.99

ā† Back to all articles