PROFIT MAXIMIZATION

Final Edition

The values of certain goods or securities (e.g., oil, gold, stocks, as well as basic commodities like flour, sugar, etc.) are shaped daily based on supply and demand, as well as on the estimation of their future trends. As a result of these transactions, these prices change from day to day. Some take advantage of this price fluctuation by buying a quantity (or right to a quantity) at a low price and then selling the same quantity or right at a higher price. Profit is expressed by the ratio of the selling price to the buying price. Suppose we know the daily price of a commodity over a long period. We want to calculate the maximum profit one could gain with a buy and sell transaction.

Problem:

Develop a program in one of the IOI languages that reads the number of days for which the commodity price is known, the price of the commodity for each of these days, and calculates the maximum possible profit from a purchase followed by a sale.

Input Files:

The input files named profit.in are text files with the following structure: The first line contains an integer ~N~, the number of days for which the commodity price is known ~(1 \le N \le 1.000.000)~. The second line contains ~N~ integers ~X_i~ (for ~1 \le i \le N~), separated by spaces, representing the price of the commodity for each day ~(1 \le X_i \le 1.000)~.

Output Files:

The output files named profit.out are text files with the following structure: They consist of one line containing a real number ~P~, which represents the maximum possible profit from a buy and sell operation, i.e., the maximum value of the ratio ~X_i / X_j~ when ~j \le i~. The number ~P~ must be rounded to three decimal places.

Examples of Input - Output Files:

1st

STDIN (profit.in)

10
5 4 3 10 11 9 8 8 8 8

STDOUT (profit.out)

3.667

Explanation of Example 1: The maximum profit is obtained if someone buys on the third day ~(X_3 = 3)~ and sells on the fifth day ~(X_5 = 11)~. The profit is ~X_5 / X_3 = 11 / 3 = 3.6666666~...

2nd

STDIN (profit.in)

10
9 8 15 5 6 9 8 10 3 5

STDOUT (profit.out)

2.000

Explanation of Example 2: The maximum profit is obtained if someone buys on the fourth day ~(X_4 = 5)~ and sells on the eighth day ~(X_8 = 10)~. The profit is ~X_8 / X_4 = 10 / 5 = 2~.

3d

STDIN (profit.in)

10
9 8 7 6 5 4 3 2 1 1

STDOUT (profit.out)

1.000

Explanation of Example 3: The product's value is consistently decreasing; therefore, it is not possible to achieve a real profit. The maximum value of the ratio is ~1~ if someone buys and sells on the same day.

Maximum Time: 1 sec