← 返回编程题库
coding-sum-subarray-mins-pnl中等免费版2000ms未尝试

P&L 子数组最小值之和

Sum of Subarray Minimum P&Ls

开始编码

某微结构组拿到一支策略当日逐分钟整数 P&L 序列 pnl。他们想要一个标量,刻画当日所有连续回看窗口下的最差分钟风险:枚举 pnl每一个连续子数组,取其最小值,再把所有最小值加起来。这个统计量对短时段深度亏损非常敏感(类似最大回撤的味道)——一笔深亏会出现在很多子数组里、主导总和;而一笔被收益包围的小亏只会作为少数子数组的最小值。为了在长会话下输出有界,组里规定结果对 10⁹ + 7 取模。

请实现 solution(pnl: list[int]) -> int,返回 (Σ_{每个连续子数组 A} min(A)) mod (10⁹ + 7)。空数组返回 0;单元素 [x] 返回 x mod (10⁹ + 7);长度 n 全等于 v 的序列返回 v * n * (n+1) / 2 mod M,因为每个 n*(n+1)/2 子数组的最小值都是 v。

示例solution([3, 1, 2, 4]) 返回 17。共 10 个子数组:3 仅是 [3] 的最小值(贡献 3);1[3,1][3,1,2][3,1,2,4][1][1,2][1,2,4] 这 6 个的最小值(贡献 6);2[2][2,4] 这 2 个的最小值(贡献 4);4 仅是 [4] 的最小值(贡献 4)。合计 3 + 6 + 4 + 4 = 17示例 2solution([7, 7, 7, 7, 7]) 返回 7 * (5*6/2) = 105,每个子数组的最小值都是 7。示例 3(负值)solution([-3, 5, -2, 4, -1]) 返回 999999987,这是 (-20) mod (10⁹ + 7)——Python 的 % 自动给出非负余数。

朴素做法(固定起点向右扩展、维护当前最小值)是 O(n²),n = 3·10⁴ 时会超时。核心技巧是「贡献法」:每个元素 pnl[i] 的贡献为 pnl[i] * (left_count + 1) * (right_count + 1),其中 left_count 是左侧严格大于 pnl[i] 的连续前驱个数,right_count 是右侧大于等于 pnl[i] 的连续后继个数。严格 / 非严格的不对称是为了避免平局重复计数——它把每个具有重复最小值的子数组规范地归给最左边的那个最小值。两边的计数各用一次单调栈扫描即可,整体 O(n) 时间、O(n) 额外空间——这是单调栈在一维时间序列统计中的典型用法。

约束条件

  • 0 ≤ len(pnl) ≤ 30000
  • -10⁹ ≤ pnl[i] ≤ 10⁹(每分钟整数 P&L)
  • 空输入返回 0
  • 输出为「所有连续子数组最小值之和」对 10⁹+7 取模后的非负整数
  • 评测使用精确比较;模数是规范的一部分,不是提示

样例

Case 1 · canonical [3,1,2,4]

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

期望: 17

共 10 个子数组:3 是 1 个子数组的最小值(贡献 3);1 是 6 个子数组的最小值(贡献 6);2 是 2 个子数组的最小值(贡献 4);4 是 1 个子数组的最小值(贡献 4)。合计 3+6+4+4=17。

Case 2 · all-equal — every subarray same min

输入: [[7,7,7,7,7]]

期望: 105

n=5,子数组共有 n*(n+1)/2=15 个,每个最小值都是 7,总和 7*15=105。

Case 3 · negative P&L — modulo gives non-negative residue

输入: [[-3,5,-2,4,-1]]

期望: 999999987

未取模总和为 -20,Python 的 % 自动归一化为 (-20) mod (10^9+7) = 999999987。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · canonical [3,1,2,4]

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

期望: 17

共 10 个子数组:3 是 1 个子数组的最小值(贡献 3);1 是 6 个子数组的最小值(贡献 6);2 是 2 个子数组的最小值(贡献 4);4 是 1 个子数组的最小值(贡献 4)。合计 3+6+4+4=17。

Case 2 · all-equal — every subarray same min

输入: [[7,7,7,7,7]]

期望: 105

n=5,子数组共有 n*(n+1)/2=15 个,每个最小值都是 7,总和 7*15=105。

Case 3 · negative P&L — modulo gives non-negative residue

输入: [[-3,5,-2,4,-1]]

期望: 999999987

未取模总和为 -20,Python 的 % 自动归一化为 (-20) mod (10^9+7) = 999999987。