Free Arrays lessonsArrays · Stage 9 · Kadane’s algorithm · Step 4

Cheapest so far

Find the best buy-then-sell profit by remembering the lowest price seen. About 8 minutes.

Sell today, having bought at the cheapest day so far

You have a share's price for each day, and you may buy once and sell once, later. What's the most you could have made?

Suppose you sell today. The best day to have bought was the cheapest day before today. So walk through the days keeping the lowest price seen so far. Each day, work out today's price minus that lowest price, and keep the best profit you've seen.

Profit if you sell today: today's price minus the lowest so far.

lowest so far → best profit

day

lowest 7. best 0.

Move 1 of 6

Not trading is allowed

If the price only ever falls, every trade loses money. The sensible choice is not to trade at all, which makes 0. So the best profit starts at 0, and a loss never replaces it.

For 7, 1, 5, 3, 6, 4: buy at 1, sell at 6, profit 5.

Start the best at 0: doing nothing beats a loss.

In code

lowest = float("inf")
best = 0
for price in prices:
    lowest = min(lowest, price)
    best = max(best, price - lowest)
return best

Quick check

The lowest price so far is 3, the best profit so far is 4, and today's price is 9. What's the best profit now?

Show the answer

6. Selling at 9 after buying at 3 makes 6, which beats 4.

Your problem

Best single trade

You get the price of a share on each day. You may buy once and sell once on a later day. Return the largest profit you can make, or 0 if no trade makes money.

Example

prices = [7, 1, 5, 3, 6, 4] → 5

0 ≤ n ≤ 1,000,000 · 0 ≤ each price ≤ 10^9

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.