A fruit seller writes down the wholesale price of mangoes every morning for n days. She may buy one crate on one day and sell it on a later day (at most one trade).
Print the largest profit she can make. If no trade makes money, print 0.
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ price ≤ 1000000
Input and output
- Input
- The first line has n. The second line has n integers: the price on each day.
- Output
- One integer: the maximum profit (0 if none).
Examples
Input 1
6
7 2 5 9 1 4Output
7Buy at 2, sell at 9.
Input 2
4
9 8 6 3Output
0Prices only fall, so the best is not to trade.
Show hints
- For each day, what is the cheapest price seen before it?
- You only need one pass.
Show the explanation
Scan the days once, keeping the lowest price seen so far. Selling today earns price - lowest; keep the best of those. Buying and selling on the same day earns 0, which is why the answer is never negative.
This is O(n) time and O(1) space, versus O(n²) for checking every pair.
Original UniCircle question. Last reviewed 22 Oct 2026.