買賣股票的最佳時機 III

給定一個數組,它的第 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;

來源:力扣(LeetCode)
鏈接://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii

Tags: