#1914. 低买高卖

低买高卖

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你有预测股票的能力:可以知道某只股票未来 N\red{N}天的价格。 你当然准备通过这项能力获利,但为了不让别人发现你的"钞能力",只打算每天最多交易一股股票。也 就是说,每天你要么买入一股,要么卖出一股(当你没有任何股票时,你就不能出售),要么什么都不 做。

最初你拥有零股,但可以融资(借钱)。在 N\red{N}天结束后,你要把借来的钱还回去,同时帐下恢复零股。

现在问题来了:通过最合理的买卖,你可以从这 N\red{N}天内赚到多少钱。

输入格式

第一行输入一个数,表示 N\red{N}

接下来一行是N\red{N }个数, pi\red{p_i}表示股票在第 i\red{i}天的价格。

输出格式

输出一个数M\red{M ,}表示这 N\red{N}天最多可以赚到的利润。

样例

输入样例1

9
10 5 4 7 9 12 6 2 10

输出样例1

20

输入样例2

20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4

输出样例2

41

提示

对于前 20%\red{20\%}的数据,N<=1000\red{N<=1000 }

对于20%30%\red{20\% \sim 30\% }的数据,1<=pi<=2\red{1<=p_i<=2 }

对于 100%\red{100\%}的数据,N<=100000\red{N<=100000 ,}1<=pi<=1000000\red{1<=p_i<=1000000 }

小云雀c++高中组重现

未参加
状态
已结束
规则
ACM/ICPC
题目
4
开始于
2022-5-3 18:00
结束于
2022-5-5 18:00
持续时间
48 小时
主持人
参赛人数
27