LeetCode: 188. Best Time to Buy and Sell Stock IV

题目描述

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:

You may not engage in multiple transactions at the same time 
(ie, you must sell the stock before you buy again).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

解题思路 —— 动态规划

思路同 LeetCode: 123. Best Time to Buy and Sell Stock III 题解。这里就不再赘述。需要注意的是，本题给定的 k 可能会很大，需要判断 k 是否大于给定数组的二倍，如果是，则用 LeetCode: 122. Best Time to Buy and Sell Stock II 题解 的算法求解。否则会 Memory Limit Exceeded。

AC 代码

class Solution
{
private:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for(int i = 1; i < prices.size(); ++i)
        {
            // 计算每天的收益
            if(prices[i] - prices[i-1] > 0) profit += (prices[i]-prices[i-1]);
        }
        return profit;
    }
public:
    int maxProfit(int k, vector<int>& prices) 
    {
        // 优化处理，避免 Memory Limit Exceeded
        if(k >= prices.size()*2) return maxProfit(prices);

        // first: 买入股票， second: 卖出股票
        vector<pair<int, int>> lastProfits;    // 上一天的记录
        vector<pair<int, int>> currentProfits; // 当天的记录
        // 初始化...
        for(int i = 0; i <= k; ++i)
        {
            lastProfits.push_back({INT_MIN, INT_MIN});
            currentProfits.push_back({INT_MIN, INT_MIN});
        }

        for(size_t i = 1; i <= prices.size(); ++i)
        {
            for(int j = 1; j <= k && j <= i; ++j)
            {
                // 第 i 天，第 j 次买入股票: 前一天买入和当天买入的价格最大值
                if(lastProfits[j-1].second != INT_MIN)
                {
                    currentProfits[j].first = max(lastProfits[j].first, 
                                             lastProfits[j-1].second - prices[i-1]);
                }
                else
                {
                    currentProfits[j].first = max(lastProfits[j].first, - prices[i-1]);
                }

                // 第 i 天，第 j 次卖出股票
                if(lastProfits[j].first != INT_MIN)
                {
                    currentProfits[j].second = max(lastProfits[j].second, 
                                              lastProfits[j].first + prices[i-1]);
                }
            }

            lastProfits = currentProfits;
        }

        int ans = 0;
        for(size_t j = 0; j <= k; ++j)
        {  
            ans = max(ans, currentProfits[j].second);
        }

        return ans;
    }
};