Ravi trades onions at a mandi. The list prices holds the price of one sack of onions on each day. prices[i] is the price on day i.
Ravi picks one day to buy a sack. Then he picks a later day to sell it. He can do this only once. Find the biggest profit he can make.
If no choice of days gives a profit, Ravi does not trade at all. In that case the answer is 0.
Examples
Example 1:
Input: prices = [120,95,130,110,160,90]
Output: 65
Explanation: Buy on day 1 at price 95. Sell on day 4 at price 160. Profit = 160 - 95 = 65. The price 90 comes after the best selling day, so it cannot be used.
Example 2:
Input: prices = [50,48,45,40,40]
Output: 0
Explanation: The price never goes up. Every trade loses money or breaks even, so Ravi does not trade.
Example 3:
Input: prices = [30,10,10,20,5,40]
Output: 35
Explanation: Buy on day 4 at price 5. Sell on day 5 at price 40. Profit = 40 - 5 = 35.