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

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

這道題實際上是之前那道 Best Time to Buy and Sell Stock III 買股票的最佳時間之三的一般情況的推廣，還是需要用動態(tài)規(guī)劃Dynamic programming來解決，具體思路如下：

這里我們需要兩個遞推公式來分別更新兩個變量local和global，我們其實可以求至少k次交易的最大利潤。我們定義local[i][j]為在到達第i天時最多可進行j次交易并且最后一次交易在最后一天賣出的最大利潤，此為局部最優(yōu)。然后我們定義global[i][j]為在到達第i天時最多可進行j次交易的最大利潤，此為全局最優(yōu)。它們的遞推式為：

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

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

其中局部最優(yōu)值是比較前一天并少交易一次的全局最優(yōu)加上大于0的差值，和前一天的局部最優(yōu)加上差值后相比，兩者之中取較大值，而全局最優(yōu)比較局部最優(yōu)和前一天的全局最優(yōu)。

但這道題還有個坑，就是如果k的值遠大于prices的天數(shù)，比如k是好幾百萬，而prices的天數(shù)就為若干天的話，上面的DP解法就非常的沒有效率，應(yīng)該直接用Best Time to Buy and Sell Stock II 買股票的最佳時間之二的方法來求解，所以實際上這道題是之前的二和三的綜合體，代碼如下：

class Solution {
public:
    int maxProfit(int k, vector<int> &prices) {
        if (prices.empty()) return 0;
        if (k >= prices.size()) return solveMaxProfit(prices);
        int g[k + 1] = {0};
        int l[k + 1] = {0};
        for (int i = 0; i < prices.size() - 1; ++i) {
            int diff = prices[i + 1] - prices[i];
            for (int j = k; j >= 1; --j) {
                l[j] = max(g[j - 1] + max(diff, 0), l[j] + diff);
                g[j] = max(g[j], l[j]);
            }
        }
        return g[k];
    }
    int solveMaxProfit(vector<int> &prices) {
        int res = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] - prices[i - 1] > 0) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
};

類似題目：

Best Time to Buy and Sell Stock with Cooldown

Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock

到此這篇關(guān)于C++實現(xiàn)LeetCode(188.買賣股票的最佳時間之四)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)買賣股票的最佳時間之四內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！