leetcode Best Time to Buy and Sell Stock with Cooldown

leetcode Best Time to Buy and Sell Stock with Cooldown

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 Best Time to Buy and Sell Stock with Cooldown 

题意:

给定一个数组prices,prices[i]代表第i天股票的价格。让你进行若干次买卖,求最大利润

  • 你每次只能买一支而且在再次买入之前必须出售之前手头上的股票(就是手头上最多有一支股票)
  • 每次出售需要休息一天才能再次买入

 

Idea

DP,we can create two array, buy and sell.

buy[i] means we decide buy or no buy a stock at day i  to  maximize profits,

and sell[i] means we sell or not sell a stock at day i to  maximize profits.

so, we have two equations :

  • buy[i] = max(buy[i-1] , sell[i-2] – prices[i])  // So we should use sell[i-2] means we cooldown one day.
  • sell[i] = max(sell[i-1], buy[i-1] + prices[i])

finally, it is obvious that sell[n-1] >= buy[n-1],so we return sell[n-1]

have more parctice in :    leetcode Best Time to Buy and Sell Stock I ~ IV

 

思路

设sell[i] 卖出操作的最大利润。它需要考虑的是,第i天是否卖出。(手上有stock在第i天所能获得的最大利润)

buy[i] 买进操作的最大利润。它需要考虑的是,第i天是否买进。(手上没有stock在第i天所能获得的最大利润)

所以,显然有状态转移方程

  • buy[i] = max(buy[i-1] , sell[i-2] – prices[i])  // 休息一天在买入,所以是sell[i-2]在状态转移
  • sell[i] = max(sell[i-1], buy[i-1] + prices[i])

最后显然有sell[n-1] > buy[n-1] 所以我们返回sell[n-1]

 

Code

C++

 

python

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Best Time to Buy and Sell Stock with Cooldown
本文地址:https://www.hrwhisper.me/leetcode-best-time-to-buy-and-sell-stock-with-cooldown/

您的支持将鼓励我继续创作!

Leetcode , , . permalink.

9 thoughts on “leetcode Best Time to Buy and Sell Stock with Cooldown

  1. 请问能讲详细解一下 buy[i] = max(buy[i-1] , sell[i-2] – prices[i]),这两种发生时的情况吗?
    我怎么感觉当buy[i] = buy[i-1] 发生时是连续两天buy了

    • 比如说 [3, 2, 1, 4, 5] 这个数据显然是在1的时买进5的时候卖出,利润为4。
      buy :[-3, -2, -1, -1, -1]
      sell : [0, 0, 0, 3, 4]

      你可以把buy想成是一个决策,什么时候买比较划算。
      price[ 2] = 1的时候买入 buy [ 2 ] = -1
      而i = 3 就是 price [ 3 ] = 4的时候 , 显然 sell[ i – 2 ] – price [ 3 ] = 0 – 4 = -4 显然不应该这时候买进,即:应该继续持有价格为 1 的时候买进的股票。而如果这时候卖出呢? 利润可以有 buy[ i – 1 ] + price [ i ] = -1 + 4 = 3
      i = 4 的时候呢? 同i = 3,持有i = 1的时候的更为划算!而卖出利润:buy[ i – 1 ] + price [ i ] = -1 + 5 = 4

  2. 解法是正确的 但是解释完全错误了。 sell[i]和buy[i]根本就不是第i天卖出和买进的意思,代表的意思是第i天手上是否有stock,分成两种状态(手上有stock在第i天所能获得的最大利润,以及手上没有stock在第i天所能获得的最大利润)。请修正。

    • 是我没讲明白,我讲的是状态转移时候要考虑的东西。 其实手上没有stock在第i天所能获得的最大利润和 考虑第i天是否卖出(以达到最大利润) 是一样的。sell是以卖出操作结尾的,但不一定非得是第i天卖出。 thanks~

Leave a Reply

Your email address will not be published. Required fields are marked *