前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode309. Best time to sell stock with cooldown

Leetcode309. Best time to sell stock with cooldown

作者头像
眯眯眼的猫头鹰
发布2018-10-31 11:07:11
2980
发布2018-10-31 11:07:11
举报
文章被收录于专栏:眯眯眼猫头鹰的小树杈

题目要求

代码语言:javascript
复制
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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

和前面几题相比,这题还增加了一个限制条件,也就是说我们在抛出股票之后,还需要冷却一天才可以买入下一只股票。那么我们进行什么样的操作才能使收益最大呢?

思路和代码

这里转述leetcode上一个非常漂亮的解答。 在第i天时,我们可以进行两种操作,抛出或是买入或是啥都不干。但是具体下来,又有四种情况:

  1. 在持有一只股票的时候抛出
  2. 在持有一只股票的时候啥都不干
  3. 在持有0只股票的时候啥都不干
  4. 在持有0只股票的时候买入

而在这些操作之间又存在潜在的联系,也就是说我如果在第i天进行以上四种操作之一,那么意味着我在第i-1天一定进行了这四种操作中的某一种,从而支持我第i天的操作。具体关联如下:

  1. 第i天执行的操作:在持有一只股票的时候抛出 => 在第i-1天执行的操作: 在持有一只股票的时候啥都不干/在持有0只股票的时候买入
  2. 第i天执行的操作:在持有一只股票的时候啥也不干 => 在第i-1天执行的操作:在持有一只股票的时候啥也不干/在持有0只股票的会后买入
  3. 第i天执行的操作:在持有0只股票的时候买入 => 在第i-1天执行的操作:在持有0只股票的时候啥也不做
  4. 第i天执行的操作:在持有0只股票的时候啥也不做 => 在第i-1天执行的操作:在持有0只股票的时候啥也不做/在持有一只股票的时候抛出

我们采用动态规划的思想,分别记录第i-1天的时候这四种情况的最大收入,并由此比较并得出第i天时这四种情况的最大收入。最后比较最后一天这四种情况可以得到的最大收益,代码如下:

代码语言:javascript
复制
    public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        int hasOneDoNothing = -prices[0];
        int hasOneSellIt = 0;
        int hasZeroDoNothing = 0;
        int hasZeroBuyOne = -prices[0];
        
        for(int i = 1 ; i<prices.length ; i++){
            int tmp1 = hasOneDoNothing;
            int tmp2 = hasOneSellIt;
            int tmp3 = hasZeroDoNothing;
            int tmp4 = hasZeroBuyOne;
            
            hasOneDoNothing = tmp1 > tmp4 ? tmp1 : tmp4;
            hasOneSellIt = (tmp1 > tmp4 ? tmp1 : tmp4) + prices[i];
            hasZeroDoNothing = tmp2 > tmp3 ? tmp2 : tmp3;
            hasZeroBuyOne = tmp3 - prices[i];
        }
        
        return hasZeroDoNothing > hasOneSellIt ? hasZeroDoNothing : hasOneSellIt;
    }

这里你可能会困惑,为什么只比较 在最后一天持有0只股票并且不进行任何操作在最后一天持有股票并抛出这两种情况呢? 假设我们最后一天持有股票并且不抛出,那么意味着在之前买入最后一只股票的那一天,如果我们不购入将会得到更大的收益。因此抛出一定比不抛出得到的损失小。 至于另一种情况,即最后一天又买入了股票,显然它一定比不买入股票得到的收益少啊。 因此我们只要比较最初提出的两种情况即可。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目要求
  • 思路和代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档