152. Maximum Product Subarray

At a Glance

• Topic: dp-1d
• Pattern: Dynamic Programming (track min and max along line)
• Difficulty: Medium
• Companies: Amazon, Google, Facebook, Microsoft, Bloomberg
• Frequency: Very High
• LeetCode: 152

Problem (one-liner)

Given integer array nums, find a contiguous non-empty subarray whose product is maximum. Input: nums. Output: that maximum product (fits in 32-bit signed by problem statement).

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• “Maximum product subarray” (not sum)
• Negatives flip sign; zeros reset segment
• Need both running max and min at each index

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — all subarrays — O(n^3) time.
• Better — segment split at zeros + brute inside — still bad on long runs without zeros.
• Optimal — single pass: carry currentMax and currentMin — O(n) time / O(1) space. <- pick this in interview.

Optimal Solution

Go

package main

func maxProductTable(nums []int) int {
	length := len(nums)
	if length == 0 {
		return 0
	}
	maxEnding := make([]int, length)
	minEnding := make([]int, length)
	maxEnding[0] = nums[0]
	minEnding[0] = nums[0]
	best := nums[0]
	for index := 1; index < length; index++ {
		value := nums[index]
		if value >= 0 {
			maxEnding[index] = max(value, maxEnding[index-1]*value)
			minEnding[index] = min(value, minEnding[index-1]*value)
		} else {
			maxEnding[index] = max(value, minEnding[index-1]*value)
			minEnding[index] = min(value, maxEnding[index-1]*value)
		}
		if maxEnding[index] > best {
			best = maxEnding[index]
		}
	}
	return best
}

func maxProduct(nums []int) int {
	length := len(nums)
	if length == 0 {
		return 0
	}
	currentMax := nums[0]
	currentMin := nums[0]
	best := nums[0]
	for index := 1; index < length; index++ {
		value := nums[index]
		nextMax := max(value, max(currentMax*value, currentMin*value))
		nextMin := min(value, min(currentMax*value, currentMin*value))
		currentMax = nextMax
		currentMin = nextMin
		if currentMax > best {
			best = currentMax
		}
	}
	return best
}

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
}

JavaScript

function maxProductTable(nums) {
  const length = nums.length;
  if (length === 0) return 0;
  const maxEnding = new Array(length);
  const minEnding = new Array(length);
  maxEnding[0] = nums[0];
  minEnding[0] = nums[0];
  let best = nums[0];
  for (let index = 1; index < length; index++) {
    const value = nums[index];
    maxEnding[index] = Math.max(
      value,
      value * maxEnding[index - 1],
      value * minEnding[index - 1],
    );
    minEnding[index] = Math.min(
      value,
      value * maxEnding[index - 1],
      value * minEnding[index - 1],
    );
    best = Math.max(best, maxEnding[index]);
  }
  return best;
}

function maxProduct(nums) {
  const length = nums.length;
  if (length === 0) return 0;
  let currentMax = nums[0];
  let currentMin = nums[0];
  let best = nums[0];
  for (let index = 1; index < length; index++) {
    const value = nums[index];
    const choicesMax = [value, currentMax * value, currentMin * value];
    const choicesMin = [value, currentMax * value, currentMin * value];
    currentMax = Math.max(...choicesMax);
    currentMin = Math.min(...choicesMin);
    best = Math.max(best, currentMax);
  }
  return best;
}

Walkthrough

Input: nums = [2, 3, -2, 4]

Another path after -2 could restart subarray; rolling max/min encodes both continuation and restart via comparing with value alone.

Edge Cases

• Single element
• Contains 0 — effectively splits array
• Mix of large magnitude negatives

Pitfalls

• Using Kadane for sum only — product needs min tracking
• Overflow if language lacks big integers (problem guarantees fit)

Similar Problems

• 53. Maximum Subarray — Kadane for sum; this problem is the product twin.
• 238. Product of Array Except Self — global prefix/suffix product trick (different question).
• 322. Coin Change — another “combine numbers along array” DP mindset (different domain).

Variants

• Minimum product subarray → symmetric (track min as objective).

Mind-Map Tags

#kadane-variant #product #min-max-dp #dp-1d #medium