LeetCode 188. Best Time to Buy and Sell Stock IVsolution

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. Subscribe to see which companies asked this question.


假设你有一个数组,它的第i个元素是一支给定的股票在第i天的价格。 设计一个算法来找到最大的利润。你最多可以完成 k 笔交易。 样例 给定价格 = [4,4,6,1,1,4,2,5], 且 k = 2, 返回 6.

solution

典型的动态规划,并且利用局部和全局最优,这种思想值得仔细体会,好好掌握。 这种局部最优与全局最优问题 global[i][j] = max(local[i][j], global[i - 1][j]) 很容易知道上面这个递推式。 关键在于求取局部最优的递推式,在本题中 local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff) 这里我们需要两个递推公式来分别更新两个变量local和global 我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润,此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润,此为全局最优 局部最优解的递推式可以这样理解:

  • 在i-1天时,正在进行第j次交易,所以我们最后一天必须将股票卖出,而且这是算在第j次交易当中的,这种情况下,local[i - 1][j] + diff,只需将i-1天的局部最优解加上最后一天卖出的差值即可,相当于将最后一次交易多延迟了一天
  • 第二种情况,就是在第i-1天进行j-1次交易的全局最优解,我们在最后一天还得进行一次交易,必须卖出,如果diff大于0,那么就在第i-1天买进,i天卖出,如果小于0,就直接在第i天买进又卖出,只是为了满足j次交易,就相当于没有交易,即加上0就可以了。 这道题还有一个陷阱,可以优化的地方,就是如果k>=prices.length/2。那我们可以理解可以进行任意次交易了,因为有效交易都需要两天来完成,所以直接使用贪心法就可以算出来了。
public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if(k <=0 || len < 2)
            return 0;
        int maxProfit = 0;
        
        if(k >= len/2) {
            //直接当作贪心处理,也就是问题2的答案
            for(int i=1;i<len;i++) {
                int diff = prices[i]-prices[i-1];
                if(diff > 0)
                    maxProfit += diff;
            }
            return maxProfit;
        }
        
        int[][] local = new int[len][k+1];
        int[][] global = new int[len][k+1];
        
        for(int i=1;i<len;i++) {
            int diff = prices[i] - prices[i-1];
            for(int j=1;j<=k;j++) {
                local[i][j] = Math.max(global[i-1][j-1] + Math.max(diff, 0), 
                        local[i-1][j] + diff);
                global[i][j] = Math.max(local[i][j], global[i-1][j]);
            }
        }
        return global[len-1][k];
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LeetCode 122. Best Time to Buy and Sell Stock IISOLUTION

很简单,既然可以进行任意次的交易,那么我们就将所有前一天比后一天价格低的都进行交易,因为只有这样,才会增加收益,所以我们进行一次遍历之后,就可以求出的最大收益值...

9410
来自专栏大数据挖掘DT机器学习

利用主成分分析构建股票指数

作者:谢佳标 中国R语言大会讲师,高级数据分析师,8年以上数据挖掘建模工作实战经验 https://ask.hellobi.com/blog/xiejiabi...

31190
来自专栏数据小魔方

用ggplot轻松搞定太极图

ggplot的图层语法给了使用者无限种可能,再配合上自己对于数据操纵的灵活把控,真的不知道ggplot可以给我们呈现出什么的惊艳作品。 这不,清明假期无聊的我,...

30220
来自专栏FreeBuf

高效幂模算法探究:Montgomery算法解析

模运算,又称模算数(modular arithmetic),是一个整数的算术系统,其中数字超过一定值后(称为模)会“卷回”到较小的数值,模运算最早是卡尔·弗里德...

73830
来自专栏专知

双人协作游戏带你理解变分自编码器-Part2

13320
来自专栏大数据文摘

机器学习单挑数学界:最新算法仲裁数列之美(附论文)

它揭示了表面看似无关的数学领域之间的深层联系,是数学界的伟大奇观之一。而这也指出了数学之美的另一个组成部分:数学模式必须在某种角度上是有趣的。

12140
来自专栏AI研习社

文本分类又来了,用 Scikit-Learn 解决多类文本分类问题

在商业领域有很多文本分类的应用,比如新闻故事通常由主题来分类;内容或产品常常被打上标签;基于如何在线谈论产品或品牌,用户被分成支持者等等。

17810
来自专栏我和未来有约会

[Silverlight动画]转向行为 - 转向机车

转向机车类继承机车类并增加转向行为。每个行为都被定义成公开函数,在每帧或者一段时间间隔内调用以实现对应的转向力。通常所有转向力在调用之后再调用机车的update...

21670
来自专栏UAI人工智能

深度学习入门教程 第一讲

18230
来自专栏海天一树

小朋友学算法(15):计算年份的天干地支

十天干:甲、乙、丙、丁、戊、己、庚、辛、壬、癸; 十二地支:子、丑、寅、卯、辰、巳、午、未、申、酉、戌、亥。

10930

扫码关注云+社区

领取腾讯云代金券