309. Best Time to Buy and Sell Stock with Cooldown

At a Glance

Topic: dp-2d
Pattern: Dynamic Programming (finite state machine on timeline)
Difficulty: Medium
Companies: Google, Amazon, Adobe, Microsoft, Uber
Frequency: High
LeetCode: 309

Given daily prices, maximize profit with unlimited transactions but cannot buy on the day immediately after you sell (1-day cooldown). You may hold at most one share. Input: prices. Output: max profit.

Recognition Cues

“Cooldown” after sell
Stock problems as states: holding, not holding (free), cooldown
Day DP transitions depend on previous state

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 — recurse sell/buy/skip — exponential.
Better — 2D dp[day][state] table — O(n) time / O(n) space.
Optimal — three scalars rolling through days — O(n) time / O(1) space. <- pick this in interview.

Optimal Solution

Go

package main

func maxProfitTable(prices []int) int {
	length := len(prices)
	if length == 0 {
		return 0
	}
	holding := make([]int, length)
	cooldown := make([]int, length)
	free := make([]int, length)
	holding[0] = -prices[0]
	cooldown[0] = 0
	free[0] = 0
	for day := 1; day < length; day++ {
		price := prices[day]
		nextHolding := holding[day-1]
		buyFromFree := free[day-1] - price
		if buyFromFree > nextHolding {
			nextHolding = buyFromFree
		}
		nextCooldown := holding[day-1] + price
		nextFree := cooldown[day-1]
		if free[day-1] > nextFree {
			nextFree = free[day-1]
		}
		holding[day] = nextHolding
		cooldown[day] = nextCooldown
		free[day] = nextFree
	}
	last := length - 1
	if cooldown[last] > free[last] {
		return cooldown[last]
	}
	return free[last]
}

func maxProfit(prices []int) int {
	length := len(prices)
	if length == 0 {
		return 0
	}
	holding := -prices[0]
	cooldown := 0
	free := 0
	for day := 1; day < length; day++ {
		price := prices[day]
		nextHolding := holding
		buyFromFree := free - price
		if buyFromFree > nextHolding {
			nextHolding = buyFromFree
		}
		nextCooldown := holding + price
		nextFree := cooldown
		if free > nextFree {
			nextFree = free
		}
		holding = nextHolding
		cooldown = nextCooldown
		free = nextFree
	}
	if cooldown > free {
		return cooldown
	}
	return free
}

JavaScript

function maxProfit(prices) {
	const length = prices.length;
	if (length === 0) return 0;
	let holding = -prices[0];
	let cooldown = 0;
	let free = 0;
	for (let day = 1; day < length; day++) {
		const price = prices[day];
		const nextHolding = Math.max(holding, free - price);
		const nextCooldown = holding + price;
		const nextFree = Math.max(cooldown, free);
		holding = nextHolding;
		cooldown = nextCooldown;
		free = nextFree;
	}
	return Math.max(cooldown, free);
}