给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
思路一:
for循环分割成两组,分别计算最大值
时间复杂度O(n2)
思路二:
五个状态
1、未买
2、买第一支股票(buy1)
3、卖第一支股票(sell1)
4、买第二支股票(buy2)
5、卖第二支股票(sell2)
由于1、始终是0,所以实际后四个状态即刻。
状态转移方程:
buy1 = max(buy1,-price[i]);
sell1 = max(sell1,buy1+price[i]);
buy2 = max(buy2,sell1-price[i]);
sell2 = max(sell2,buy2+price[i]);
由于股票可以在同一天不断买入卖出
所以初始化时
buy1 = -price[0];
sell1 = 0;
buy2 = -price[0];
sell2 = 0;