[LeetCode] Best Time to Buy and Sell Stock IV 买卖股票的最佳时间之四-阿里云开发者社区

开发者社区> 李博 bluemind> 正文

[LeetCode] 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,参见网友Code Ganker的博客,我们其实可以求至少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 买股票的最佳时间之二的方法来求解,所以实际上这道题是之前的二和三的综合体,代码如下:

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;
    }
};

 本文转自博客园Grandyang的博客,原文链接:买卖股票的最佳时间之四[LeetCode] Best Time to Buy and Sell Stock IV ,如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LeetCode 380: 常数时间插入、删除和获取随机元素 Insert Delete GetRandom O(1)
题目: 设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。 insert(val):当元素 val 不存在时,向集合中插入该项。 remove(val):元素 val 存在时,从集合中移除该项。
693 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9497 0
WCF客户端和服务器时间不一致,导致通道建立失败的问题)
本文转载:http://www.cnblogs.com/bcbr/articles/2288374.html   最近,经常有客户反应,前天还用的好好的系统,今天就不能用了。考虑到系统近来没有做过改动和升级操作,所以从客户的机器环境入手解决,最后发现客户端的日期时间和服务端的日期时间有较大差异,将客户端机器修改成和服务端的日期时间一致后,系统恢复正常。
769 0
jQuery日期和时间插件(jquery-ui-timepicker-addon.js)中文破解版使用
简介 jQuery UI Datepicker日期选择插件很好用了,只不过只能精确到日,不能选择时间(小时分钟秒)很遗憾,而jquery-ui-timepicker-addon.js正是基于jQuery UI Datepicker的一款可选时间的插件。
1090 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13186 0
+关注
李博 bluemind
云栖社区Java、Redis、MongoDB运营小编,有意合作请联系钉钉:15810436147
2107
文章
1103
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载