題目： LeetCode - 123. Best Time to Buy and Sell Stock III

題目說明

給一個陣列代表每日的股票價格，求買賣兩次後的最高收益。當手上有一支股票時就無法買第二支股票。

解題思路

動態規劃，轉移方程為：

1
2
3
4
cost1 = min(p, cost1);
profit1 = max(p - cost1, profit1);
cost2 = min(p - profit1, cost2);
profit2 = max(p - cost2, profit2);

將 profit1 的收益與 cost2 結合，profit2 即為最後的總收益，

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int cost1 = INT_MAX, cost2 = INT_MAX;
        int profit1 = 0, profit2 = 0;
        for(auto p : prices)
        {
            cost1 = min(p, cost1);
            profit1 = max(p - cost1, profit1);
            cost2 = min(p - profit1, cost2);
            profit2 = max(p - cost2, profit2);
        }
        return profit2;
    }
};