[LeetCode] 188.Best Time to Buy and Sell Stock IV 買(mǎi)賣股票的最佳時(shí)間之四

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.

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

這里我們需要兩個(gè)遞推公式來(lái)分別更新兩個(gè)變量local和global，我們其實(shí)可以求至少k次交易的最大利潤(rùn)。我們定義local[i][j]為在到達(dá)第i天時(shí)最多可進(jìn)行j次交易并且最后一次交易在最后一天賣出的最大利潤(rùn)，此為局部最優(yōu)。然后我們定義global[i][j]為在到達(dá)第i天時(shí)最多可進(jìn)行j次交易的最大利潤(rùn)，此為全局最優(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)。

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

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++實(shí)現(xiàn)LeetCode(188.買(mǎi)賣股票的最佳時(shí)間之四)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)買(mǎi)賣股票的最佳時(shí)間之四內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論