← 返回编程题库
coding-max-strict-monotone-reward-subseq-sum中等免费版2000ms未尝试

最小步长递增日内收益子序列的最大累计和(阶梯 PnL 上限)

Max Sum of a Min-Step-Monotone Reward Subsequence (Stair-Step PnL Ceiling)

开始编码

实现 solution(reward: list[int], min_step: int) -> int。给定长度为 N 的每日收益序列 reward 与最小步长参数 min_step,选取一组下标 i_1 < i_2 < ... < i_KN >= 1K >= 1;不要求连续),要求每对相邻下标满足 reward[i_{k+1}] >= reward[i_k] + min_step,并最大化 reward[i_1] + reward[i_2] + ... + reward[i_K]。返回该最大和。

N == 0 返回 0(空子序列约定,和为 0)。否则返回所有合法非空子序列中累计和的最大值。注意单点选取永远合法(长度 1 的链没有相邻对约束需要检查),所以即便所有元素都是负数,答案也是 max(reward)不是 0

solution([3, 1, 4, 1, 5, 9, 2, 6], 2) 返回 17。最优选点是下标 0, 4, 5,对应 reward 为 3, 5, 9——每一个后续选点比前一个至少高 25 >= 3 + 29 >= 5 + 2),累计和 3 + 5 + 9 = 17。对比:选 0, 2, 4, 5(reward 3, 4, 5, 9——4 >= 3 + 2 不成立,非法);选 2, 5(reward 4, 9,和 13);只选 9。这些都不及 17。若把 min_step 改成 0,链可放宽到非严格,能容纳 4 点链 3, 4, 5, 9,和为 21;若把 min_step 改成 100,任何长度 2 的链都不可能,答案塌缩到 max(reward) = 9

实践背景

研究台对一个候选信号模型做归因诊断,把模型在固定股票池上每日的"假设性" PnL 贡献摆出来。研究主管想要一个"阶梯 PnL"上限——所有日子的子集中,使得所选每一天的当日 reward 至少比前一所选日的 reward 高 min_step 时,可达到的累计 reward 最大值。把 min_step 校准到模型每日 PnL 的噪声水平,可以让该指标区分"真正的递增超额收益"与"恰好单调但量级噪声水平内的小幅改进":min_step = 0 时退化为 LIS 族上限——任何非递减链都算;当 min_step 设为模型每日 PnL 一两倍标准差时,只有产出"显著大于自身噪声的赢家"的连续段才计入上限。研究主管以"捕获率"口径用该上限作为评估基准——若实盘 PnL 能捕获 min_step 校准下上限的 60%,说明该模型在选定的显著性阈值下确实在产出递增赢家序列;而若用平凡的 sum(max(0, r) for r in reward) 做基准,会把"持平或微正天数"也算进去,造成模型评分虚高。

实现细节由 stubs/stub.py 提供。

约束条件

  • 0 <= N <= 1500,其中 N 是传入 solution(reward, min_step) 的 reward 数组长度
  • 每个 reward[i] 为有符号整数,-1000000 <= reward[i] <= 1000000
  • 0 <= min_step <= 4000000;min_step 是相邻选点 reward 必须达到的最小增幅(绝对单位)。min_step == 0 时允许等值(非严格);min_step >= 1 时禁止等值;min_step 足够大时任何长度 2 的链都不可能存在
  • 输出为有限整数。N == 0 返回 0(空子序列约定);N >= 1 永远返回最大和,当不存在满足 min_step 谓词的长度 2 的链时,该最大和等于 max(reward)
  • 无异常路径:任何满足上述边界的输入都会得到有限整数输出;比较器为整数精确相等

样例

Case 1 · statement-example: min_step=2 picks idx 0,4,5 for sum 17

输入: [[3,1,4,1,5,9,2,6],2]

期望: 17

最优选点是下标 0, 4, 5,对应 reward 3, 5, 9(每步至少高 2),累计和 3+5+9 = 17。

Case 2 · statement-corner: empty reward returns 0 regardless of min_step

输入: [[],5]

期望: 0

空输入按空子序列约定返回 0。

Case 3 · statement-corner: all-negative rewards with min_step=0 -> max single pick

输入: [[-10,-1,-100],0]

期望: -1

全负输入下,单点子序列永远合法;最大单值为 -1。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · statement-example: min_step=2 picks idx 0,4,5 for sum 17

输入: [[3,1,4,1,5,9,2,6],2]

期望: 17

最优选点是下标 0, 4, 5,对应 reward 3, 5, 9(每步至少高 2),累计和 3+5+9 = 17。

Case 2 · statement-corner: empty reward returns 0 regardless of min_step

输入: [[],5]

期望: 0

空输入按空子序列约定返回 0。

Case 3 · statement-corner: all-negative rewards with min_step=0 -> max single pick

输入: [[-10,-1,-100],0]

期望: -1

全负输入下,单点子序列永远合法;最大单值为 -1。