Buying and selling stocks

Given n integers that represent the stock prices of your favorite company, you’d like to decide what would be the best time to buy and sell the stock. You would like to buy the stock only once and sell it only once. So, you’d like to maximize the profit (buy low and sell high).
Determine the maximum possible profit you can make on your favorite company, and if there is no way to do so, you should print 0 (meaning you won’t buy or sell that stock).


The first line of the input contains a single integer n (1 ≤ n ≤ ).
The next line contains space-separated integers representing the prices of the stock (0 ≤ ≤ 1000).


The program should print the maximum possible profit you can make on buying and selling your favorite stock.


5 4 2 6 8 1
4 8 6 4 3


  1. We buy when the stock value is 2 and we sell it when it’s 8
  1. We won’t be able to make any profit as the stock value constantly declines
At each point, you can keep a state of the current “best” possible answer and another value for the cheapest the stock has ever been.


Time limit: 2.4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in