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).

Recognition Cues

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

Diagram

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

Loading diagram…

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;
}