← 返回编程题库
coding-max-reward-trades-min-gap中等免费版2000ms未尝试

在合规冷却期约束下的最大累计收益(带时间戳的候选交易)

Maximum Total Reward From Timestamped Trade Candidates Under A Compliance Hold-Period Gap

开始编码

实现 solution(trades: list[list[float]], gap: int) -> float。每条记录形如 [time:int, reward:float],候选列表**按 time 升序排序**(允许并列)。挑选一个候选的子集(每条至多取一次),使任意两条被取出的候选 i < j 满足 time[j] - time[i] >= gap(两次执行之间的合规冷却时间)。返回最大累计收益(float)。负收益候选可以不取;若所有 reward 都为负,最优解为 0.0(一条都不取)。空 trades 返回 0.0gap == 0 表示无间隔约束,每条严格正收益候选都取。

例:solution([[0, 1.0], [1, 2.0], [5, 3.0]], 3) 返回 5.0。三条候选位于 time 0、1、5;当 gap = 3 时,time 0 与 time 1 的两条互斥(间隔 1 < 3),但两者各自都与 time 5 那条相容(间隔分别是 5 与 4,皆 >= 3)。所以最优是从前两条中选 reward 较大的那一条——time 1 的 2.0——再叠加 time 5 的 3.0,合计 5.0。如果改选 time 0 + time 5 只有 4.0;三条全取不可行。

测试用例显式区分的边界:gap = 0 退化为"严格正收益之和"(不需要 DP);time 并列在 gap >= 1 时互斥;所有 reward 为负时返回 0.0;最大隐藏样例 N = 2000,覆盖密集时间戳、并列时间戳与稀疏时间戳三类。complexity_target 字段记录的 O(N log N) 是参考算法;在 N <= 2000 的本套测试规模下,O(N log N)O(N^2) 的 Python 实现都能在每测 2000 ms 预算内通过。

solution 必须校验"按 time 升序"这一前置条件,对任意逆序对抛 ValueError(合约简洁——是否预排序由调用方负责)。函数骨架见 stubs/stub.py

实践背景

很多交易台会接入一条预筛选后的"交易想法"流——每条都打上预定执行时间与一个带符号的预期收益(alpha 减去预期 slippage 与融资成本)——然后必须遵守一个监管或自定的"合规冷却期":一次执行之后,同一个交易台(或同一个策略账册、或同一个标的桶)必须等至少 gap 秒才能再发下一笔。原因可以是抑制 market-impact 反馈环、自我强加的洗售墙、或限制下单路由的吞吐。给定该冷却期,交易台想知道当天预筛后的候选里,到底要把哪些真的触发执行才能最大化预期累计收益——而且关键是:预期收益为负的想法(比如对冲在当前成本水平下的成本超过 alpha 贡献)可以直接不取。这个数字并非实时可交易策略(需要预知当天完整候选列表),但它是该交易台合规体制下可达上界,被用作 idea-capture ratio(想法捕获率)的分母,给在线分发器打分:捕获到 0.7 倍上界的路由器,在冷却期窗口里挑想法挑得相当靠谱;只捕获到 0.2 的就明显把价值漏掉了。

约束条件

  • 0 <= N <= 2000,其中 N 为传入 solution(trades, gap) 的 trades 长度
  • 0 <= gap <= 1_000_000_000;gap 为整数;gap == 0 表示无合规间隔约束
  • 每条记录形如 [time:int, reward:float],0 <= time <= 1e9 且 -1e6 <= reward <= 1e6 有限;trades 必须按 time 升序排序(允许并列)——否则 solution 抛出 ValueError
  • 输出为有限浮点数(与 reward[] 同单位的总收益);比较器为 float,rel_tol = 1e-9,abs_tol = 1e-12
  • 空 trades 与所有 reward 都为负的 trades 都精确返回 0.0

样例

Case 1 · statement-example: gap=3 picks time-1 + time-5 = 2.0+3.0

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

期望: 5

gap=3 下,time 0 与 time 1 互斥(间隔 1<3),各自与 time 5 相容;最优取 time 1 的 2.0 + time 5 的 3.0 = 5.0。

Case 2 · statement-example: gap=0 sums all positives ignoring spacing

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

期望: 6

gap=0 表示无间隔约束,所有正收益直接累加:1+2+3=6.0。

Case 3 · statement-example: empty trades returns 0.0

输入: [[],5]

期望: 0

空 trades 直接返回 0.0。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · statement-example: gap=3 picks time-1 + time-5 = 2.0+3.0

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

期望: 5

gap=3 下,time 0 与 time 1 互斥(间隔 1<3),各自与 time 5 相容;最优取 time 1 的 2.0 + time 5 的 3.0 = 5.0。

Case 2 · statement-example: gap=0 sums all positives ignoring spacing

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

期望: 6

gap=0 表示无间隔约束,所有正收益直接累加:1+2+3=6.0。

Case 3 · statement-example: empty trades returns 0.0

输入: [[],5]

期望: 0

空 trades 直接返回 0.0。