A single share of a stock has a known price on each of n consecutive trading days. You may buy the share on one day and sell it on a strictly later day, at most once. If no purchase-then-sale earns a positive profit, you simply do not trade.
Return the maximum profit you can make.
Line 1: an integer n, the number of days.
Line 2: n space-separated non-negative integers, the price on each day (present whenever n >= 1).
A single integer: the maximum achievable profit, or 0 if every possible sale would lose money or break even.
Example 1
Input
6 7 1 5 3 6 4
Expected
5
Explanation
Buy on the day priced 1 and sell on the later day priced 6 for a profit of 5. No other buy-before-sell pair beats 5.
Example 2
Input
5 9 7 5 3 1
Expected
0
Explanation
Prices only fall, so every later day is cheaper than an earlier one. No profitable trade exists, so the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →