J16 习题-8 股票买卖1

题目描述

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

输入格式

第一行一个整数$T$，表示一共有 $T$ 组数据； 对于每组数据： 第一行是一个整数 $N$ ，表示未来 $N$ 天内操作。 第二行 $N$ 个整数，表示每天该股票的价格 $A_i$ 。

输出格式

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

样例输入

3
6
7 1 5 3 6 4
5
1 2 3 4 5
5
7 6 4 3 1

样例输出

7
4
0

样例分析

样例1：在第 $2$ 天（股票价格 $= 1$）的时候买入，在第 $3$ 天（股票价格 = $5$）的时候卖出, 这笔交易所能获得利润 $= 5-1 = 4$ 。随后，在第 $4$ 天（股票价格 $= 3$）的时候买入，在第 $5$ 天（股票价格 $= 6$）的时候卖出, 这笔交易所能获得利润 $= 6-3 = 3$ 。共得利润 $4+3 = 7$。

样例2：在第 $1$ 天（股票价格 = $1$）的时候买入，在第 $5$天 （股票价格 $= 5$ ）的时候卖出, 这笔交易所能获得利润 $= 5-1 = 4$ 。注意你不能在第 $1$ 天和第 $2$ 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

样例3：在这种情况下, 不进行任何交易, 所以最大利润为 $0$。

数据范围

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