Problem B
Predicting GME
GME is the stock market ticker symbol for Gamestop, which is famously known around the world today for its short squeeze phenomenon. This incident caused major financial consequences for rich hedge funds, and brought money to many young, naive investors.
Sarah recently became interested in GME, and managed to obtain a list of predicted prices for the stock in the next $N$ days. Due to the high volume of trades happening with GME, major stock brokers have put out the following restrictions:
-
Only one transaction may be completed on a given day.
-
After selling, you will not be able to buy on the next day.
-
You may only hold one stock at any given time.
Write Sarah a program that can return the maximum profit while considering the restrictions put in place.
Input
Input consists of two lines. The first will contain the number of predictions, $N$ ($1 \leq N \leq 10^3$) made for each day. The second line consists of $N$ space separated integers with a predicted value between $0$ and $10^3$.
Output
Output the maximum profit that can be made from the predictions provided.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 2 0 1 4 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 5 3 1 2 6 8 1 2 |
7 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 1 |
0 |
