B. 最大和 详细题解

题目核心理解

给定一个长度为 $n$ 的数组 $a$，需要执行恰好 $k$ 次操作。 每次操作可以选择任意连续子数组（可以为空），求出它的和并插入数组任意位置。

求 $k$ 次操作后，数组能达到的最大可能和，结果对 $10^9+7$ 取模。

核心思路

1. 关键符号与性质

设：

• $s$：原数组所有元素的和
• $x$：数组的最大子段和（空子数组的和为 $0$，若所有子段和为负则取 $0$）

最优策略：

• 每次操作都选择当前最大子段和并插入数组。
• 每次插入后，新的最大子段和会变为原来的 $2$ 倍。

2. 增量规律

• 第 $1$ 次插入：新增 $x$
• 第 $2$ 次插入：新增 $2x$
• 第 $3$ 次插入：新增 $4x$
• ……
• 第 $k$ 次插入：新增 $2^{k-1}x$

总增量是等比数列求和：

算法流程

1. 计算原数组的总和 $s$。
2. 使用贪心算法（Kadane）求出数组的最大子段和 $x$，并与 $0$ 取最大值。
3. 用快速幂计算 $2^k \bmod (10^9+7)$。
4. 代入公式计算最终答案。
5. 将结果对 $10^9+7$ 取模并输出（保证非负）。

公式与复杂度分析

最终答案公式：

复杂度

• 求数组和与最大子段和：$O(n)$
• 快速幂计算 $2^k$：$O(\log k)$
• 总时间复杂度：$O(n + \log k)$

可轻松处理 $n,k \le 2\times10^5$、多组数据总和限制。