A wholesale desk can lift one lot of copper from the mill on a single session and dump it on a later close. Compliance forbids shorting: you cannot sell a lot you have not bought. The intern version nested every pair of days — buy on i, sell on every j > i. A week of closes returned instantly. A year of hourly ticks was still looping when the risk report was due.

One buy, then one later sell: maximize the spread. An array already gives prices[i] for free. Nested pairing uses that and still pays O(n²). The global min and the global max of the whole series are the wrong shortcut: the cheap day might sit after the expensive one, and you cannot sell first.

This is an interview writeup, not a named-algorithm lecture. You walk left to right, remember the lowest price so far, and ask what today’s close would pay against that floor.

The problem

Given an int[] prices where prices[i] is the quote on day i, you may buy once and sell once on a strictly later day. Return the largest profit that pairing can make. If no later day beats the buy, return 0.

prices = [9, 3, 8, 1, 7]   →  6    buy 1 (day 3), sell 7 (day 4)
prices = [4, 7, 2, 9]      →  7    buy 2, sell 9
prices = [8, 6, 5, 4]      →  0    every later close is worse

Note: Day order is the constraint. A sell index must be greater than the buy index. Same-day round-trip is profit 0; it never beats a real later spread, and it never rescues a falling series.

Nested pairs are the honest brute force

Every legal (buy, sell) pair is visited once. Correct. Quadratic.

int maxProfitNested(int[] prices) {
    int best = 0;
    for (int i = 0; i < prices.length; i++) {
        for (int j = i + 1; j < prices.length; j++) {
            best = Math.max(best, prices[j] - prices[i]);
        }
    }
    return best;
}

At n = 20 this is a rounding error. At n in the tens of thousands you paid a nested scan for a question one running minimum answers in a single pass: best later close against the cheapest day so far?

One pass: floor so far, best spread so far

Walk left to right. Two running values:

  • minSoFar — the lowest price on any day up to and including today. That is the only buy you still need.
  • maxProfit — the best today - minSoFar seen so far. Starts at 0 so a falling series stays at no-trade.

You never restart a scan from day 0. You never pair today with a future close you have not reached. Sell-before-buy cannot happen because the floor is taken from the prefix, not from the whole array.

prices = [9, 3, 8, 1, 7]

day 0  p=9   min=9   profit=0
day 1  p=3   min=3   profit=0
day 2  p=8   min=3   profit=5     8 - 3
day 3  p=1   min=1   profit=5
day 4  p=7   min=1   profit=6     7 - 1

The Java is that walk:

int maxProfit(int[] prices) {
    int minSoFar = Integer.MAX_VALUE;
    int maxProfit = 0;
    for (int p : prices) {
        minSoFar = Math.min(minSoFar, p);
        maxProfit = Math.max(maxProfit, p - minSoFar);
    }
    return maxProfit;
}

Time is O(n) — one pass, constant work per day. Space is O(1) besides the two running integers.

Note: Do not take min and max of the whole array. On [9, 3, 8, 1, 7] the global min is 1 and the global max is 9, but 9 is earlier. The prefix floor is what makes the later 7 - 1 legal. When p is a new min, p - minSoFar is 0 that day and maxProfit does not move — that is the same-day no-op, not a trade.

What interviewers usually poke next

  • Empty or a single day. The loop never finds a later close. Return 0. No special case required.
  • Cannot sell the same day. Profit 0 on that day already. If they forbid it as a rule, the answer does not change.
  • Multiple buys and sells (II). A different problem. This prompt is one buy, one later sell. Do not start summing every up-tick unless they change the statement.
  • Cooldown, or a fee. Names of later variants. Say they change the recurrence; do not invent the DP at this board unless they ask.
  • Daily deltas. If they rewrite the series as prices[i] - prices[i - 1], the one-pass max subarray of those deltas is Kadane. Same profit, different framing — mention it, do not re-derive it here.

You are done with this problem when you can say, out loud, why every pair of days is correct, why the global min/max is not, and why the running floor is taken from the prefix you have already walked.