Best Time to Trade

prices[i] is the price of a share on day i. You may buy one share on one day and sell it on a later day. Return the largest profit you can make. If no sale makes money, return 0 (you don't trade).

Constraints

  • 1 ≤ length of prices ≤ 100,000
  • 0 ≤ prices[i] ≤ 10,000

Example 1

Input
prices = [7,1,5,3,6,4]
Output
5
Why:

Buy on day 1 at 1 and sell on day 4 at 6.

Example 2

Input
prices = [7,6,4,3,1]
Output
0
Why:

Prices only fall, so the best is not to trade.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –