|| ||Code Submission Evaluation System
HIIT Open 2018
Tasks | Messages | Scoreboard | Statistics
CSES - HIIT Open 2018 - Buy Low, Sell HighCSES - Buy Low, Sell High
Buy Low, Sell High
|Time limit:||1.00 s|
|Memory limit:||512 MB|
You know the stock price of a company during the next $n$ days.
You will buy and sell a single share exactly two times
during the period. More precisely, you will do as follows:
- You buy a share on day $a$ and sell it on day $b$ where $a \le b$.
- You buy a share on day $c$ and sell it on day $d$ where $b \le c \le d$.
How much money will you earn if you act optimally?
The first input line has an integer $n$: the number of days.
The second line has $n$ integers $p_1,p_2,\dots,p_n$: the stock prices.
Print one integer: the maximum profit.
- $1 \le n \le 5 \cdot 10^5$
- $1 \le p_i \le 10^9$
4 2 3 5 1 4 2 7
Explanation: First you buy a share on day 2 and sell it on day 4. Then you buy a share on day 5 and sell it on day 8.
Explanation: First you buy a share on day 1 and sell it on day 2. Then you buy a share on day 2 and sell it on day 2.