问题 3414 --股票买卖2

3414: 股票买卖2

时间限制: 1 Sec  内存限制: 256 MB
提交: 6  解决: 4
[提交][状态][讨论版][命题人:]

题目描述

给定一个长度为N的数组,数组中的第i个数字表示一个给定股票在第i天的价格。

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为1天)。

输入

第一行包含整数N,表示数组长度。

第二行包含N个不超过10000的非负整数,表示完整的数组。

输出

输出一个整数,表示最大利润。

样例输入

5
1 2 3 0 2

样例输出

3

提示

1≤N≤10^5

来源

[提交][状态]