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。示例 2:solution([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 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
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。