青岛黄岛网站建设,wordpress内置编辑器,员工信息查询系统,免费版个人简历问题#xff08;中等#xff09;
给定一个整数数组prices#xff0c;其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下#xff0c;你可以尽可能地完成更多的交易#xff08;多次买卖一支股票#xff09;:
卖出股票后中等
给定一个整数数组prices其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:
卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 来源力扣LeetCode 链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 示例 1
输入: prices [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2
输入: prices [1] 输出: 0
提示 1 p r i c e s . l e n g t h 5000 1 prices.length 5000 1prices.length5000 0 p r i c e s [ i ] 1000 0 prices[i] 1000 0prices[i]1000
解题
思路
BP问题太折磨了思路参考官方解答 每一天可以有三个状态买、卖和冷冻期
temp[i]表示截至第i天最后一个操作是卖时的最大收益 buy[i]表示截至第i天最后一个操作是买时的最大收益 frozen[i]表示截至第i天最后一个操作是冷冻期时的最大收益 递推公式 temp[i] max(buy[i-1]prices[i], temp[i-1]) (第一项表示第i天卖出第二项表示第i天冷冻) buy[i] max(frozen[i-1]-prices[i], buy[i-1]) 第一项表示第i天买进第二项表示第i天冷冻 frozen[i] max(temp[i-1], buy[i-1], frozen[i-1])
代码实现
class Solution:def maxProfit(self, prices: List[int]) - int:n len(prices)if n 0:return 0 temp [0]*nbuy [0]*nfrozen [0]*nbuy[0] -prices[0]for i in range(1,n):temp[i] max(buy[i-1] prices[i], temp[i-1])buy[i] max(frozen[i-1] - prices[i], buy[i-1])frozen[i] max(temp[i-1], buy[i-1],frozen[i-1])return temp[-1]
