Stock market
A stock company wants to create a study about the worst financial decisions during a period of time to make sure that in the future they avoid making the same mistakes. However manual analysis takes a lot of time and is prone to errors, thus they decided to hire you to create an application to automate this task.
Your job is to create a program which takes a couple stock transactions as an input and gives the highest potential loss as an output.
Note: we say that something is a financial loss if for two transactions the following is true: the profit for the "sooner" transaction is lower than the profit for the "later one". E.g. if Steve buys some stocks at 2022. october 15. for 1000 dollars and sells them at 2022. november 20. for 300 dollars then he has a financial loss of 700 dollars which is denoted by "-700". However if the same stock worths only 200 dollars at 2022. december 24. then the highest amount of financial loss is 800 dollars which we denote by "-800".
Input
- The first line of the input is a positive integer N which gives the number of stock transactions in the time period.
- The second line of the input consists of N integers, separated by a single space. These give the profit of each transaction. The transactions are ordered in time, which means the first (0th) value corresponds to the first transaction (the oldest one) and the last value corresponds to the last one (the most recent one).
Output
- A single integer which gives the maximum financial loss for the given dataset with a negative sign (so if the maximum loss is 500 dollars from 800 to 300 then the output should be -500).
- If there are no financial losses in the given dataset then output 0.
Restrictions
- 0 < N < 100000
- Every single transaction has a non-negative integer profit and each separate profit is at most 2^{31}.
Example
Explanation
The potential financial losses are the following:
3 -> 2 : the financial loss is "1"
3 -> 2 -> 4 -> 2: the financial loss is "1"
3 -> 2 -> 4 -> 2 -> 1: the financial loss is "2"
2 -> 4 -> 2 -> 1: the financial loss is "1"
4 -> 2 : the financial loss is "2"
4 -> 2 -> 1 : the financial loss is "3"
2 -> 1: the financial loss is "1"
The highest financial loss is 3, thus the output is -3.