J16 实践-9 股票买卖2

题目描述

佩奇在玩《模拟人生》的游戏，她已经能准确预测出了某只股票在未来 $N$ 天的价格！现在佩奇有无限的虚拟货币，并希望通过两次的买卖操作，使得获得的利润最高。 为了计算简单起见，利润的计算方式为卖出的价格减去买入的价格，同一天可以进行多次买卖。但是在第一次买入之后，必须要先卖出，然后才可以第二次买入。 请编程算出，佩奇最多可以获得多少利润。

输入格式 第一行是一个整数 $N$ ，表示未来 $N$ 天内操作。 第二行 $N$ 个整数，表示每天该股票的价格 $A_i$ 。

输出格式

一个整数，表示佩奇获得的最大利润。

样例输入

7
5 14 -2 4 9 3 17

样例输出

28
2
0

样例分析 佩奇可以第一次在第 $1$ 天买入（价格为 $5$ ），然后在第 $2$ 天卖出（价格为 $14$ ）； 第二次在第 $3$ 天买入（价格为 $-2$ ），然后在第 $7$ 天卖出（价格为 $17$ ）。 一共获得的利润是： $(14 - 5) + (17 - (-2)) = 28$ 。 其他数据，以此类推。

数据范围

对于 $100\%$ 的数据， $1 \leq n \leq 10^5;-10^6 \leq A_i \leq 10^6$。