最佳买卖股票时机含冷冻期 leetcode-309

最佳买卖股票时机含冷冻期 leetcode-309



func maxProfit(prices []int) int {
 length := len(prices)
 // 特殊判断
 if length <= 1 {
  return 0
 }
 // 声明dp
 dp := make([][3]int, length)      //dp[i][j]表示[0, i]区间内,在下标为i这一天状态为j时的最大收益。
 // 初始化
 dp[0][0] = 0          // 【0天】【不持股】
 dp[0][1] = -prices[0] // 持股的初始化值为 -prices[0](表示购买了一股)【0天】【持股】
 dp[0][2] = 0          // 【0天】【冷冻期】

 for i := 1; i < length; i++ {            //0 表示不持股1 表示持股;2 表示处在冷冻期。
  // 【第i天】【不持股】 = max(昨天不持股今天不操作,昨天持股+今天卖一股)
  dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
  // 【第i天】【持股】 = max(昨天持股今天不操作,昨天冷冻期+今天买一股)
  dp[i][1] = max(dp[i-1][1], dp[i-1][2]-prices[i])
  // 【第i天】【冷冻期】 = 昨天卖了不持股
  dp[i][2] = dp[i-1][0]
 }

 // 返回不持股和冷冻期的最大者
 return max(dp[length-1][0], dp[length-1][0])
}

func max(x, y int) int {
 if x > y {
  return x
 }
 return y

上一篇:309最佳买卖股票时机含冷冻期(动态规划)


下一篇:Web微信