[LeetCode][Hard] 123. Best Time to Buy and Sell Stock III

Leetcode 網址: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

題目說明:

給定一個長度為 n 的序列，序列內的第 i 個數字代表第 i 天股票 A 的價格，

投資人被允許這 n 天內最多執行 2 次完成的交易 (買進 + 賣出算一次完整的交易)，

請設計一個演算法找出最大的獲利。

Note: 交易所限制買進時，手上必須沒有股票。

Example 1:
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

解題說明:

遇到這種題目一開始沒有想法的話就先將 input 變小，

例如思考長度為 n 的序列之最大獲利要如何從 n - 1 中的序列推出呢 ?

思考了之後可以發現長度為 n 的序列之最大獲利可以分成二個情況:

1. 最大獲利的交易是否包含第 n 天 ? 如果不包含那答案就跟 n - 1 序列的最大獲利相同

2. 最大的獲利交易包含第 n 天，那麼我們就從 n - 1 的序列中找出最便宜的價格買進，並於第 n 天賣出

有以上的想法就可以把這想法寫成演算法囉 ~

程式碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp[3][prices.size() + 1];
        memset(&dp[0][0], 0x0, sizeof(int) * 3 * (prices.size() + 1));
        for (int i = 1; i <= 2; i++) {
            int maxPrice = INT_MIN;
            for (int j = 0; j < prices.size(); j++) {
                maxPrice = max(maxPrice, -prices[j] + dp[i - 1][j]);
                dp[i][j + 1] = max(dp[i][j], prices[j] + maxPrice);
            }
        }
        return dp[2][prices.size()];
    }
};

結果

Runtime: 128 ms, faster than 97.12% of C++ online submissions for Edit Distance.

Memory Usage: 76.4 MB, less than 59.12% of C++ online submissions for Edit Distance.