喵神的股票

发布时间: 2018年1月29日 10:26   最后更新: 2018年2月11日 23:54   时间限制: 2000ms   内存限制: 128M

喵神最近在关注股票,为了计算股票可能的盈利,他获取了一只股票最近$n$天的价格$a_1,a_2,…,a_n$。喵神每天可以在下列三种操作中选取一种:

  1. 什么也不做;
  2. 按照当天的价格买进一个单位的股票;
  3. 按照当天的价格卖出部分或所有的股票。

现在喵神想知道,如果在$n$天前手中持有的股票数为$0$,并且假设有无限的金钱,在这$n$天结束能够获得的最大利润是多少?

有多组测试数据(数据组数$≤10$)。对于每组数据,第一行有一个整数$n$,第二行有$n$个整数$a_1,a_2,…,a_n$。
$1≤n≤10^6$
$1≤a_i≤100$

对于每组测试数据,输出这$n$天结束能够获得的最大利润。

复制
5
1 2 3 4 5
10

本题的输入数据量较大,建议使用高效的读写方式:C++使用scanf/printf代替cin/cout,Java使用BufferedReader/PrintWriter代替Scanner/System.out。

basic algorithm

Weekly Training 2018.1.28