Best Time to Buy and Sell Stock

Introduction

A daily stock-price series. One buy, one sell, in that order. Find the largest profit you can lock in. The brute force is obvious — try every pair — and gets to a correct answer in $O(n^2)$. The optimal answer is short enough to fit in seven lines, and the move from one to the other is exactly the kind of insight an interviewer is timing you on.

The deeper reason this problem keeps appearing is that it’s the gateway to a whole DP family. Once you’ve seen the running-state trick that makes a single buy/sell linear, the same trick generalizes to two transactions, k transactions, transactions with cooldown, transactions with a fee — half a dozen LeetCode hard problems collapse to variations on the recurrence you write here.

The interview move is asking what part of the past actually matters for the future. Once you can answer that in one number, the algorithm is linear and the chapter is over.

If you’re early in DP prep, walk both approaches in order. If you’ve coded the running-min answer before, jump to the follow-ups table — the family of harder buy/sell variants is the senior content.

What the interviewer is actually testing

1. Spotting the redundancy in brute force. A nested loop computes prices[j] - prices[i] for every pair; the same prices[i] value appears in many of those subtractions. Naming the redundancy is the optimization prompt.
2. The running-state idea. At day $j$, the only fact about the past you need is the cheapest price seen so far. Everything else can be discarded. That’s a constant-state DP.
3. Initialization discipline. A common bug initializes the running min to prices[0] and starts the loop at $j = 1$. Cleaner: initialize minSoFar = INT_MAX, loop from $i = 0$, and the first iteration handles itself.
4. Knowing the family exists. Buy/Sell II (unlimited transactions), III (at most two), IV (at most $k$), with cooldown, with fee. Naming them out loud signals you’ve been deeper into DP than the median candidate.

Problem statement

Clarifying questions — and why each one matters

A mental framework — what does the past actually tell you?

Walk through the brute-force logic and ask: what about the past does day $j$ care about?

To evaluate “what’s the best profit if I sell on day $j$?”, you need to know the cheapest day to have bought before. Just one number. Not the whole price history; not the second-cheapest; not the average. The single fact min(prices[0..j-1]) is the entire useful summary of the past.

That observation collapses the problem. Walk the prices left to right, maintaining a running minimum. At each day, the candidate profit is prices[j] - minSoFar. Track the largest candidate seen and you have the answer in one pass.

This is the template for constant-state DP: the recurrence depends on a fixed-size summary of the past. Maximum Subarray follows the same shape (running endingHere). Climbing Stairs follows it (the previous two values). The buy/sell family follows it (a small set of running profits, indexed by transaction state).

Discussion

#include <algorithm>
#include <vector>

int maxProfit(const std::vector<int>& prices) {
    const int n = static_cast<int>(prices.size());
    int best = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            best = std::max(best, prices[j] - prices[i]);
        }
    }
    return best;
}

#include <algorithm>
#include <climits>
#include <vector>

int maxProfit(const std::vector<int>& prices) {
    int minSoFar = INT_MAX;
    int best = 0;
    for (const int p : prices) {
        minSoFar = std::min(minSoFar, p);
        best = std::max(best, p - minSoFar);
    }
    return best;
}

Approach comparison

Default answer: the running-min sweep. Name the invariant — “after each day, minSoFar is the cheapest price seen and best is the maximum profit over pairs ending at any prefix” — and the code writes itself.

Follow-ups to anticipate

The buy/sell family is one of the richest follow-up trees in interview DP. Each variant changes the state, but the running-state pattern survives.

Pattern recognition — constant-state DP, again

This problem teaches the same move as Maximum Subarray and Climbing Stairs: a recurrence that depends on a fixed-size summary of the past becomes a constant-space sweep. The fixed-size summary here is just one integer (minSoFar); for harder variants it grows to two or three; for the $k$-transaction problem it grows to $k$.

Other problems that fit the same shape:

• Maximum Subarray (Kadane’s). Running endingHere and best. One number from the past.
• Climbing Stairs. The two previous values. Constant state, two integers.
• House Robber. $f(i-1)$ and $f(i-2)$. Two integers, same shape.
• Largest Rectangle in Histogram with cumulative widths. Constant per-cell state with a monotonic stack on the side.
• Reservoir sampling for top-1. Track the single running candidate; the rest of the stream is summarized by it.

The reflex: when a problem walks an array left-to-right and asks for the “best” something over all prefixes, ask what’s the smallest summary of the prefix I’d need to answer the question? If that summary is constant-size, you have an $O(n)$ / $O(1)$ algorithm.

What to say out loud — the delivery script

Ten beats:

1. “Let me restate: given a price series, find the maximum profit on a single buy-then-sell pair, or 0 if no profitable trade exists.”
2. Ask: “single transaction? no-trade returns 0? profit or pair?”
3. “Brute force enumerates every $(i, j)$ with $i < j$ and tracks the max spread — $O(n^2)$. Let me name it and look for something faster.”
4. “For each candidate sell day, the only fact about the past I need is the cheapest price seen so far. That’s a single integer of state.”
5. “So I walk left to right with two running values: minSoFar and best. On each day, update the floor, then try selling today against it.”
6. Write the code — five lines. “The order matters: update minSoFar first, then compute the candidate profit. That way the day where the new minimum was set evaluates to 0, never negative.”
7. Trace example 1 on the whiteboard. Show that the running min drops to 1 on day 1 and the best profit hits 5 on day 4.
8. “Complexity: $O(n)$ time, $O(1)$ space. The pass is sequential and cache-friendly.”
9. “Edge cases: empty array, strictly decreasing prices, all same — all return 0 by the natural mechanics. No special-casing needed.”
10. “For follow-ups: this is the gateway to the buy/sell DP family — multiple transactions, cooldown, fees. Each variant adds running states but keeps the constant-space sweep shape.”

Summary

The single-transaction buy/sell problem is short to state, short to solve, and reveals a pattern that generalizes across half a dozen harder variants. The interview signal isn’t the seven-line code; it’s articulating the move from “compare every pair” to “remember one number from the past.” That move is the constant-state DP recipe, and recognizing it is what makes the rest of the buy/sell family — multiple transactions, cooldowns, fees, $k$-bounded — feel like rotations of a single template rather than five independent problems.

The wider lesson: when an algorithm walks a sequence and asks for the best answer over all prefixes, ask first what part of the past is actually load-bearing for the future. Often it’s a single running number. When it is, the algorithm is linear and the chapter is over.