服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C++实现LeetCode(188.买卖股票的最佳时间之四)

C++实现LeetCode(188.买卖股票的最佳时间之四)

2021-12-10 15:20Grandyang C/C++

这篇文章主要介绍了C++实现LeetCode(188.买卖股票的最佳时间之四),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下

[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 买股票的最佳时间之三的一般情况的推广,还是需要用动态规划Dynamic programming来解决,具体思路如下:

这里我们需要两个递推公式来分别更新两个变量local和global,我们其实可以求至少k次交易的最大利润。我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润,此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润,此为全局最优。它们的递推式为:

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]),

其中局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值,和前一天的局部最优加上差值后相比,两者之中取较大值,而全局最优比较局部最优和前一天的全局最优。

但这道题还有个坑,就是如果k的值远大于prices的天数,比如k是好几百万,而prices的天数就为若干天的话,上面的DP解法就非常的没有效率,应该直接用Best Time to Buy and Sell Stock II 买股票的最佳时间之二的方法来求解,所以实际上这道题是之前的二和三的综合体,代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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

到此这篇关于C++实现LeetCode(188.买卖股票的最佳时间之四)的文章就介绍到这了,更多相关C++实现买卖股票的最佳时间之四内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!

原文链接:https://www.cnblogs.com/grandyang/p/4295761.html

延伸 · 阅读

精彩推荐