Maximum Profit

Given an array of stock prices where the i-th element represents the price of a stock on day i, you are required to calculate the maximum profit that can be achieved by buying and selling the stock only once. The profit is defined as the difference between the selling price and the buying price.

If no profit can be made, the answer should be 0. Mathematically, the problem is to find \[ \max_{0 \leq i < j < n} (\text{price}[j] - \text{price}[i]) \]

Note that the trading must be done in order, that is, the buying has to come before the selling.

inputFormat

The input is read from stdin and consists of two lines:

• The first line contains a single integer n, representing the number of days.
• The second line contains n space-separated integers representing the stock prices on each day. If n is 0, then no stock prices are provided and the output should be 0.

outputFormat

Output a single integer to stdout which represents the maximum profit possible from one transaction. If no profit is possible, output 0.

6
7 1 5 3 6 4

5