NeetCode #108LC-122MediumArrays & HashingNC 250
← Back to All Problems#108 · #122 · Best Time to Buy and Sell Stock II(买卖股票的最佳时机 II)
📌 Problem Statement & Constraints
You are given an array
prices where prices[i] is the price of a stock on day i. You may complete as many transactions as you like (buy one and sell one share multiple times), but you may not hold more than one share at a time. Return the maximum profit. Constraints: 1 <= prices.length <= 3 * 10^4, 0 <= prices[i] <= 10^4.💡 Core Algorithmic Approaches
- With unlimited transactions and no cooldown or fee, the optimal strategy decomposes completely: capture every upward move.
- Think of the price curve. Any profitable multi-day hold can be split into the sum of its consecutive daily gains, so holding across a dip only loses money.
- Therefore the answer is simply the sum of
max(0, prices[i] - prices[i-1])over all days. - A DP formulation also works (
holdandcashstates) and generalises to the constrained variants, but it is unnecessary here.
💻 Benchmark Python3 Implementation
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1] # capture every rise
return profit
# DP formulation: generalises to cooldown / fee / k-transaction variants
class Solution2:
def maxProfit(self, prices: List[int]) -> int:
cash = 0 # max profit with no share held
hold = -prices[0] # max profit while holding one share
for p in prices[1:]:
cash = max(cash, hold + p) # sell today
hold = max(hold, cash - p) # buy today
return cash⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): a single pass. The greedy version does one comparison per day; the DP version does two.
💾 Space Complexity
O(1): the greedy version needs one accumulator, the DP version two state variables.
⚠️ Interview Pitfalls & Follow-ups
- Over-engineering with DP: it is correct but the greedy insight is the expected answer. Mention DP only as the generalisation path.
- Trying to find local minima and maxima explicitly: it works but requires lookahead and edge handling; summing positive deltas is equivalent and simpler.
- Confusing this with the single-transaction version (121): there the answer is the best single rise, which requires tracking the running minimum.
- Subtracting negative deltas: only positive daily changes are captured; a falling day contributes 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.