土拨鼠炒果子2
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Background
土拨鼠结婚后迷上了炒果子, 他想通过炒"果子"获取更多的收益改变生活, 土拨鼠只能选择 某一天 买入这只果子，并选择在 某一天 卖出该果子。设计一个算法来计算你所能获取的最大利润。
Description
在每一天, 你都可以买入或者卖出果子, 在任何时候你最多只能持有一个果子, 你也可以在今天买入今天卖出. 但是你不可以在没有果子的时候卖出果子. 计算买卖的最大利润.
Format
Input
第1行为n
第2行为n个元素的一个数组 a ，它的第 i 个元素 a[i] 表示果子第 i 天的价格。
Output
你可以从交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
Samples
样例1
6
7 1 5 3 6 4
7
样例2
5
1 2 3 4 5
4
样例解析
样例1解释：在第 2 天（果子价格 = 1）的时候买入，在第 3 天（果子价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后，在第 4 天（果子价格 = 3）的时候买入，在第 5 天（果子价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。
Limitation
1 <= n <= 10^5
0 <= a[i] <= 10^4
