← 返回编程题库
coding-optimal-cooldown-period-trades中等免费版2000ms未尝试

强制冷静期下的最优多次交易

Optimal Cooldown Period Trades

开始编码

某中频策略组刚刚被合规上了一条新规:任何标的卖出后必须强制冷静一个交易日才能再次买入——监管想压一压日内换手率。策略组手上有未来 N 天对某支股票的价格预测序列 prices(按交易日升序,单位元/股),希望在这条冷静期约束下,事后算出最多能赚多少。规则:(1)任意时刻最多持仓一股,要先全部卖掉才能再买;(2)卖出当天之后整整一个交易日不能买入(如果第 3 天卖,最早第 5 天才能买);(3)允许做任意多次完整的「买—卖」对,也允许整个区间不交易;(4)期末不应继续持有,必须落袋为安。请算出最优累计收益

请实现 solution(prices: list[float]) -> float。当 len(prices) < 2,或所有可行策略都亏损时,返回 0.0(即「整个区间不交易」)。

示例solution([1.0, 2.0, 3.0, 0.0, 2.0]) 应返回 3.0。最优执行是:第 0 天买 (-1.0)、第 1 天卖 (+2.0)、第 2 天冷静、第 3 天买 (-0.0)、第 4 天卖 (+2.0),累计收益 2.0 - 1.0 + 2.0 - 0.0 = 3.0。如果忽略冷静期约束,本应在第 0 天买、第 2 天卖(赚 2)、再第 3 天买、第 4 天卖(再赚 2),共 4.0;但冷静期把第 3 天的入场堵死了,只剩 3.0 这条次优路径。再看 solution([3.0, 2.0, 1.0]):价格单调下跌,任何「先买后卖」都亏,最优策略是不交易,返回 0.0

朴素地枚举所有「买—卖」对组合是指数级,不可行。关键观察是每一天结束时只可能处于三种状态之一——持仓 / 刚卖出冷静中 / 空仓且自由——而下一天的状态只依赖前一天(最多前两天)的状态。一遍 O(n) 扫描即可。这个题是「无限次交易」问题(每段上涨贪心累加)的进化版:冷静期约束让贪心失效,必须用 DP 显式追踪「今天能不能买」这个隐藏自由度。

约束条件

  • 0 ≤ len(prices) ≤ 100000
  • 0 < prices[i] ≤ 10⁶(正实数报价,单位:元/股)
  • 同一时刻最多持有一股(`hold` 状态是布尔,不允许加仓)
  • 卖出当天之后必须**完整休息一天**才能再次买入(即 sell 在第 j 天,下一次 buy 最早在第 j+2 天)
  • 不强制必须交易;若所有可行策略都亏损,返回 `0.0`
  • 返回值允许 1e-6 的浮点误差

样例

Case 1 · example with cooldown forcing a suboptimal split

输入: [[1,2,3,0,2]]

期望: 3

执行:第 0 天买 (-1.0)、第 1 天卖 (+2.0)、第 2 天冷静、第 3 天买 (-0.0)、第 4 天卖 (+2.0),累计 3.0。如果没有冷静期,第 0 天买、第 2 天卖再第 3 天买、第 4 天卖能拿到 4.0;冷静期约束封死了第 3 天紧邻入场的机会,剩 3.0 这条次优路径。

Case 2 · monotonically decreasing — do not trade

输入: [[3,2,1]]

期望: 0

价格一路下跌,任何「先买后卖」都亏。规则允许整个区间不交易,最优收益是 0.0,而不是负数。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · example with cooldown forcing a suboptimal split

输入: [[1,2,3,0,2]]

期望: 3

执行:第 0 天买 (-1.0)、第 1 天卖 (+2.0)、第 2 天冷静、第 3 天买 (-0.0)、第 4 天卖 (+2.0),累计 3.0。如果没有冷静期,第 0 天买、第 2 天卖再第 3 天买、第 4 天卖能拿到 4.0;冷静期约束封死了第 3 天紧邻入场的机会,剩 3.0 这条次优路径。

Case 2 · monotonically decreasing — do not trade

输入: [[3,2,1]]

期望: 0

价格一路下跌,任何「先买后卖」都亏。规则允许整个区间不交易,最优收益是 0.0,而不是负数。