[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).

思路：

這道題目自己沒有獨立做出來，我在網上參考了兩種最好的解法，這裡和大家分享。

1、記錄局部最優解和全局最優解的動态規劃法：用local[i][j]表示到達第i天時，最多進行j次交易的局部最優解；用global[i][j]表示到達第i天時，最多進行j次交易的全局最優解。它們兩者的關系如下（其中diff = prices[i] - prices[i - 1]）：

local[i][j] = max(global[i-1][j-1] + max(diff, 0),  local[i-1][j] + diff);

global[i][j] = max(global[i-1][j], local[i][j]);

其中的local[i-1][j] + diff就是為了避免第i天交易和第i-1天交易合并成為一次交易而少一次交易收益。算法的時間複雜度是O(n^2)，空間複雜度也是O(n^2)。不過由于local和global的遞推公式隻和它臨近的元素有關，是以目測空間複雜度還可以進一步降低到O(n)。這裡偷個懶，不弄了。

2、記錄買入賣出的動态規劃法：可以記錄k次交易每次買入之後和賣出之後最大的利潤。第i次買操作買下目前股票之後剩下的最大利潤為第(i-1)次賣掉股票之後的利潤 - 目前的股票價格，狀态轉移方程為：buys[i] = max(sells[i - 1] - current_price, buys[i]). 第i次賣操作賣掉目前股票之後剩下的最大利潤為第i次買操作之後剩下的利潤 + 目前的股票價格。狀态轉移方程為：sells[i] = max(buys[i] + current_price, sells[i])。最終所求即為sells[k]。

代碼：

1、記錄局部最優解和全局最優解的動态規劃法：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.size() < 2) {
            return 0;
        }
        int days = prices.size();
        if(k >= days / 2) {
            return maxProfit(prices);
        }
        vector<vector<int>> local(days, vector<int>(k + 1, 0));
        vector<vector<int>> global(days, vector<int>(k + 1, 0));
        for(int i = 1; i < days; ++i) {
            int diff = prices[i] - prices[i - 1];
            for(int j = 1; j <= k; ++j) {
                local[i][j] = max(global[i-1][j-1], local[i-1][j] + diff);
                global[i][j] = max(global[i-1][j], local[i][j]);
            }
        }
        return global[days - 1][k];
    }
private:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0;
        for(int i = 1; i < prices.size(); ++i) {
            if(prices[i] > prices[i-1]) {
                max_profit += prices[i] - prices[i-1];
            }
        }
        return max_profit;
    }
};
           

2、記錄買入賣出的動态規劃法：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.size() < 2) {
            return 0;
        }
        int days = prices.size(), ret = 0;
        if(k >= days / 2) {
            return maxProfit(prices);
        }
        vector<int> buys(days + 1, INT_MIN);
        vector<int> sells(days + 1, 0);
        for (int i = 0; i < days; ++i) {
            for (int j = 1; j <= k; ++j) {
                buys[j] = max(sells[j - 1] - prices[i], buys[j]);
                sells[j] = max(buys[j] + prices[i], sells[j]);
            }
        }
        return sells[k];
    }
private:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0;
        for(int i = 1; i < prices.size(); ++i) {
            if(prices[i] > prices[i-1]) {
                max_profit += prices[i] - prices[i-1];
            }
        }
        return max_profit;
    }
};