在一家农场,有一群牛,每头牛都有一个市场价值,这个价值每天都会变化。农场主人可以选择在某一天买入一头牛,然后在某一天卖出。但是,农场主人最多只能进行三次买卖(买入和卖出算一次买卖),并且在买入新的牛之前必须已经卖掉手头上的牛。 现给你一个数组,表示每一天牛的市场价值,设计一个算法来计算农场主人最多能获得多少利润。
示例1

输入

[3,3,5,0,0,3,1,4,6,4,8,3]

输出

12

说明

在第 4 天(牛的市场价值 = 0)的时候买入,在第 6 天(牛的市场价值 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。然后,在第 7 天(牛的市场价值 = 1)的时候买入,在第 10 天 (牛的市场价值 = 6)的时候卖出,这笔交易所能获得利润 = 6-1 = 5。最后,在第 11 天(牛的市场价值 = 4)的时候买入,在第 13 天 (牛的市场价值 = 8)的时候卖出,这笔交易所能获得利润 = 8-4 = 4。

备注:
1 0
加载中...