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).
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ ).The next line contains space-separated integers
Output
The program should print the maximum possible profit you can make on buying and selling your favorite stock.
Examples
Input | Output |
5
4 2 6 8 1 | 6 |
4
8 6 4 3 | 0 |
Explanation
- We buy when the stock value is 2 and we sell it when it’s 8
- We won’t be able to make any profit as the stock value constantly declines
Hint
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.
Constraints
Time limit: 2.4 seconds
Memory limit: 512 MB
Output limit: 1 MB