Maintained by Vikas Dulgunde, software engineer
You are given an array where the value at each index is the stock price on that day. You may buy once and sell once, and the sale must happen on a day after the purchase. The goal is the maximum profit achievable from a single buy-then-sell pair.
Profit for any chosen pair is the selling price minus the buying price. Because selling has to come after buying, you cannot just subtract the global minimum from the global maximum if the maximum appears before the minimum in the array.
If prices only ever fall, or every later price is at most the lowest price seen so far, there is no way to come out ahead. In that case the answer is 0, meaning the best move is to make no trade at all.
Buy at 1 (day 1) and sell at 6 (day 4) for a profit of 5. Buying earlier at 7 or later at 3 would yield less.
Prices only decline, so every later price is below every earlier one. No trade beats doing nothing, so the result is 0.
Buy at 2 and sell at 4 for a profit of 2. The later price of 1 is below the buy price, so it does not help.
Visible test cases
The buy day must come before the sell day, so think about scanning left to right and asking what is the best sale you could make if you sold today.
To sell well today you only need the cheapest price seen on any earlier day, not the full history.
Track the lowest price so far and the best profit so far as you walk the array once. Update the minimum when you see a cheaper price, otherwise check whether selling now beats your current best.
Try every valid buy day paired with every later sell day and keep the largest difference.
Walk the array once while remembering the cheapest price seen so far; at each day the best possible sale equals the current price minus that running minimum.