问题 J: J

问题 J: J

时间限制: 1 Sec  内存限制: 128 MB
提交: 87  解决: 54
[状态] [讨论版] [提交] [命题人:]
题目描述

小L又一次通过超能力获知了某只股票未来N天的价格走势,这一次他可以进行任意多次交易,但是不能同时参与多次交易(即必须在再次购买前卖出当前所持有的基金)。请你帮他计算出这次最多可以获得多少收益。

输入

多组测试数据,遇到EOF结束。
每组测试数据第一行是一个正整数N(0<=N<=103),接下来N个整数代表这只基金未来N天的价格(1<=价格<=104)。 

输出

对于每组测试数据输出其最大收益。

样例输入 Copy
6
7 1 5 3 6 4
5
1 2 3 4 5
样例输出 Copy
7
4
提示

第一组:在第 2 天(基金价格 = 1)的时候买入,在第 3 天(基金价格 = 5)的时候卖出, 这笔交易所能获得利润= 5-1 = 4。随后,在第 4 天(基金价格 = 3)的时候买入,在第 5 天(基金价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

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