Maximum Product Subarray in Go: Why the Running Max Isn't Enough

Day 25/75: Maximum Product Subarray -- the running max is not enough

75 Day DSA in Go Challenge

I reused the wrong algorithm and it taught me more than getting it right would have. I was scoring growth-factor streaks -- a slice of per-step multipliers like [2, 3, -2, 4] where each number is how much a position grew or shrank that step -- and I wanted the best contiguous window by product. Max-sum Kadane was fresh in my head, so I carried one running value, took max(x, cur*x) each step, and kept the best. It worked on the first slice, then returned 3 on [-2, 3, -4]. The correct answer is 24, the product of the whole slice.

Why SUM and PRODUCT diverge

With a maximum-sum subarray, only a small running total can hurt you. Addition never reorders values, so tracking just the maximum is safe -- that is plain Kadane. Product is different: a single negative flips the sign of everything it touches. Your largest running product becomes your smallest, and a large-negative smallest becomes your largest the instant the next value is also negative. The minimum is not noise to discard. It is a candidate for the next maximum.

The broken trace

func maxProductBroken(nums []int) int {
    best, cur := nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        x := nums[i]
        if cur*x > x {
            cur = cur * x
        } else {
            cur = x
        }
        if cur > best {
            best = cur
        }
    }
    return best
}

On [-2, 3, -4]: start cur = -2. At 3, max(3, -6) = 3. At -4, max(-4, -12) = -4, best stays 3. But -2 * 3 * -4 = 24. The scan discarded the -6 it held at step two -- and -6 * -4 = 24 was the answer it should have reported.

Track both ends

Carry curMax (largest product ending here) and curMin (smallest). When the next number is negative, multiplying by it turns the largest into the smallest and vice versa, so swap them before the update.

package main

import "fmt"

func maxProduct(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    best := nums[0]
    curMax, curMin := nums[0], nums[0]

    for i := 1; i < len(nums); i++ {
        x := nums[i]
        if x < 0 {
            curMax, curMin = curMin, curMax // negative reorders the extremes
        }
        // candidates: extend the running product, or restart at x
        if curMax*x > x {
            curMax = curMax * x
        } else {
            curMax = x
        }
        if curMin*x < x {
            curMin = curMin * x
        } else {
            curMin = x
        }
        if curMax > best {
            best = curMax
        }
    }
    return best
}

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

I wrote the updates as explicit if branches here rather than max/min calls so the restart-or-extend decision is visible: at each step the candidate is either the running product times x, or x standing alone as a fresh window.

Re-trace the fix

[-2, 3, -4]: start curMax = curMin = best = -2. At 3 (positive, no swap): curMax = max(3, -6) = 3, curMin = min(3, -6) = -6, best = 3. At -4 (negative, swap first → curMax = -6, curMin = 3): curMax = max(-4, -6*-4) = 24, curMin = min(-4, -12) = -12, best = 24. The -6 carried as curMin is what produced 24.

Zero and seeding

A zero kills any product through it, so both ends should reset. The extend-or-restart form does this for free: at a zero, curMax*x and curMin*x are both 0 and the restart picks 0, so the window starts fresh on the far side. On [-2, 0, -1] the answer is 0. And seed best with nums[0], never 1 -- a single-element [-3] must return -3, and an identity seed of 1 would report 1 for an all-negative odd-length slice.

Complexity and the division trap

One forward pass, three scalars: O(n) time, O(1) space. No prefix-product array. And no division -- division is the seductive shortcut for product problems (prefix-product, divide to drop the current element), but it detonates the instant a zero appears, and these inputs are full of zeros and negatives. The escort-the-minimum approach sidesteps all of it.

The transferable idea

When your combining operation can reorder values, the extreme you are not optimizing for is still a live candidate. Sum never reorders -- max-only Kadane is safe. Product reorders on every negative -- so the minimum rides along beside the maximum, and you swap them the moment a negative shows up. The tell: a max-only scan returning a too-small answer on a slice with negatives means you dropped a minimum that was one sign flip from winning.