Best Time to Buy and Sell Stock

You get the price of one stock over a run of days, one price per day. You may buy one share on some day and sell it on a later day. The profit is the selling price minus the buying price, and you want the biggest profit possible. If every trade would lose money, you simply do not trade and earn 0.

Take the prices [7, 2, 5, 9, 1, 4]. Buying at 2 on day 1 and selling at 9 on day 3 earns 7, and no other pair of days does better. Buying at 1 on day 4 looks tempting because it is the cheapest day, but the only later day sells for 4, so that trade earns just 3.

Trying every pair of days works, but it is far too slow for long price lists. You can do it in one walk through the days instead. If you sell today, the best day to have bought is the cheapest day so far, so keep that lowest price as you go. Today's best profit is today's price minus the lowest price, and the answer is the largest of those.

Write a function named maxProfit that gets a list of integers prices, where prices[i] is the stock's price on day i, and returns the largest profit you can make by buying on one day and selling on a later day. If no trade makes a profit, return 0.

Constraints: 1 ≤ prices.length ≤ 10^5, 0 ≤ prices[i] ≤ 10^4.