北京
2026-09-15：M 个非重叠子数组最大和Ⅰ。用go语言，给定一个整数序列 nums，其长度为 n，同时还给出三个整数 m、l、r。现在需要从 nums 中挑出若干个连续的非空片段，这些片段之间不能重叠，也不能共用同一个位置。挑出的片段数量最少为 1 个，最多为 m 个。每个被挑出的片段，其长度必须不小于 l，且不大于 r，也就是长度要落在闭区间 [l, r] 内。目标是让所有被挑中片段里的整数加起来的总和尽可能大。最后返回这个能够得到的最大总和。这里的片段，指的就是原序列中连续排列的一段非空元素。
1 <= n == nums.length <= 1000。
-1000000000 <= nums[i] <= 1000000000。
1 <= m <= n。
1 <= l <= r <= n。
输入： nums = [4,1,-5,2], m = 2, l = 1, r = 3。
输出： 7。
解释：
一种最优策略是：
选择子数组 [4, 1]，其和为 4 + 1 = 5；再选择子数组 [2]，其和为 2。两个子数组的长度都在 [l, r] 范围内。
这些子数组的总和为 5 + 2 = 7，这是在至多 m = 2 个子数组下能够取得的最大总和。
题目来自力扣3956。
一、先把问题翻译成一个可递推的模型
题目要在数组里挑1 到 m 段、彼此不重叠、每段长度在[l, r]内的连续片段，使总和最大。
一个很自然的想法是：不要直接求"至多 m 段"，而是按段数分层去求——
先算出"恰好选 1 段"的最优解，再算"恰好选 2 段"的，……直到"恰好选 m 段"。因为每层都算出了全局（取满整个数组前 n 个数）的最优值，最后在 1..m 层里取一个最大值，就自然等价于"至多 m 段"的最优解。
这就是代码里ans = max(ans, f[n])放在每一层循环末尾的原因：用"恰好 i 段"的最大值去刷新"至多 m 段"的答案。
于是核心变成：定义状态f[i][j]=只在前 j 个数（下标 0 ~ j-1）里挑，恰好挑 i 段，能得到的最大总和。
二、预处理：前缀和
原数组nums，构造前缀和数组s，长度为 n+1，其中s[0] = 0，s[t] = nums[0] + ... + nums[t-1]。
这样任意一段nums[k ... j-1]的和就能O(1)算出来：s[j] - s[k]。
这一步是后面所有快速计算的地基。注意nums[i]可达 ±10⁹、n 可达 1000，总和会到 ±10¹² 量级，所以返回值类型是int64（在 64 位平台上int也够用，但返回时显式转成了 int64）。
三、状态转移（先不管优化，把方程写对）
考虑f[i][j]，也就是"前 j 个数里选 i 段"的最优值，看最后一个元素nums[j-1]的命运，只有两种可能：
情况 A：不把它选进来。
那么这 i 段全部落在前 j-1 个数里，最优值就是f[i][j-1]。这一项同时也自动允许了段与段之间留有间隔——不是每段都必须紧贴着上一段。
情况 B：把它选进来，而且它必须是第 i 段的末尾。
那么第 i 段形如nums[k ... j-1]，起点是某个 k。这一段的长度是j - k，必须满足l ≤ j - k ≤ r，即：
k 的取值范围：j - r ≤ k ≤ j - l
而前面的 i-1 段必须全部塞在 k 的左边（不重叠），它们的最优值恰好就是f[i-1][k]。所以这种情况下的总收益是：
f[i-1][k] + (s[j] - s[k])
把所有合法 k 都试一遍取最大，再和情况 A 取最大，就得到完整转移：
f[i][j] = max( f[i][j-1] , max over k∈[j-r, j-l] 的 ( f[i-1][k] - s[k] + s[j] ) )
关键的观察：在这个 max 里，s[j]对于固定的 j 是常数，可以提出来：
f[i][j] = max( f[i][j-1] , s[j] + max over k∈[j-r, j-l] 的 ( f[i-1][k] - s[k] ) )
也就是说，对每个 j，我们只需要回答一个滑动窗口的最大值问题：
在下标区间 [j-r, j-l] 这个窗口里，哪个 k 让 f[i-1][k] - s[k] 最大？
朴素做法是每次遍历整个窗口，代价 O(r-l)；而窗口宽度固定、随 j 单调右移——这正是单调队列的标准战场。
四、单调队列：把每个 j 的窗口最大值压到摊还 O(1)
代码里的q就是那个单调队列。它存的是候选起点下标 k，并且始终保持一个性质：
队列里各 k 对应的值 f[k] - s[k]（这里的 f 是上一层，即 i-1 层）从队首到队尾严格递减。队首永远是当前窗口的最大值。
每一轮 j 循环，队列做三件事，顺序固定为入 → 查 → 出：
1. 入队（窗口右端向右扩）
当 j 前进 1 时，合法 k 的上界j - l也跟着 +1，于是新冒出来一个候选 k = j - l，要把它塞进队列。
塞之前先做单调性维护：从队尾开始，只要队尾那个 k' 满足f[k'] - s[k'] ≤ f[k] - s[k]，就把队尾弹出。理由是——这个老候选 k' 的值不如新来的 k，而且它比 k 更早滑出窗口（k' 更小），所以它此后再也不可能在任何窗口里当上最大值，留着纯属浪费。一直弹到队尾比新值大（或队列空）为止，再把 k 放到队尾。
2. 查询（用队首更新答案）
此时队首q[0]就是窗口[j-r, j-l]中使f[k] - s[k]最大的 k。于是：
nf[j] = max( nf[j-1] , f[队首] - s[队首] + s[j] )
前一项是"不选 nums[j-1]"，后一项是"选一个以 j-1 结尾、起点为队首的第 i 段"。两者取大，就是新的f[i][j]（代码里用nf表示"正在算的这一层"）。
3. 出队（为下一轮清掉过期元素）
更新完nf[j]后，j 马上要变成 j+1，那时的合法下界是k ≥ (j+1) - r = j - r + 1。所以凡是k ≤ j - r的队首元素，从下一轮起就永远不合法了，现在就该踢掉：
若 队首 ≤ j - r，则队首出队。
放在"更新之后"做，等价于在下一轮"入队之前"清理，逻辑完全等价，只是写起来更顺。
为什么是摊还 O(1)
每个 k 在一整层 i 里最多入队一次、出队一次（队尾弹出的元素再也不会回来）。所以一整层的所有出队操作加起来是 O(n)，而不是每次 O(窗口宽度)。这就是从 O(m·n·r) 降到 O(m·n) 的关键。
五、滚动数组：把空间从 O(m·n) 压到 O(n)
观察转移式：f[i][j]只依赖上一层f[i-1][*]和本层已经算出来的f[i][j-1]。所以根本不需要保存完整的二维表，只要两个一维数组：
•
f：上一层（i-1 段）的结果，只读；•
nf：正在计算的这一层（i 段），只写。
每层算完，f = nf，进入下一层。这就是代码里f和nf两个长度为 n+1 的一维数组的由来。
六、几个容易踩坑的边界细节
（1）j 的起点为什么是i * l
选 i 段、每段至少长 l，总共至少占用i × l个位置。前 j 个数若j < i×l，根本放不下 i 段，状态无意义。这样既剪掉了无效循环，又保证了后面用到的k = j - l ≥ (i-1)×l——也就是说f[k]一定是上一层里真实有效的状态（上一层 j 也是从(i-1)×l开始的），不会取到"无意义的负无穷"去污染转移。
（2）负无穷的取法nf初始化成math.MinInt / 2而不是math.MinInt，是为了留足余量：后面还会拿它和f[k] - s[k]做加法、比较，如果直接用最小整数，一旦再减点什么就会下溢绕回成正数，导致结果荒谬。除以 2 是常见的防御写法。ans初始化成math.MinInt是安全的，因为第 1 层必定能算出合法解（l ≤ n，j 至少能取到 j = l），ans 第一次就会被真实值覆盖。
（3）"至多 m 段"的处理
每层 i 结束都用本层的f[n]（恰好 i 段、覆盖整个数组的最优值）去刷新 ans。这样 1 段、2 段、……、m 段全部被考虑过，取到的最大值自然就是"至多 m 段"的答案。
（4）i = 0 的初始状态f在第一次进入循环前是 Go 的零值，也就是全 0：表示"选 0 段、总和为 0"，对任意 j 都成立。这也让第 1 层的转移f[k] - s[k] = -s[k]天然正确。
（5）队列不会空
每次都是先"入队一个 k"再"用队首更新"，所以取队首时队列一定非空。即便l == r导致入队的元素在"出队"步骤里被立刻弹掉，下一轮也会先补一个新的 k 进来，不影响。
七、用样例走一遍
nums = [4, 1, -5, 2]，m = 2，l = 1，r = 3，n = 4
前缀和s = [0, 4, 5, 0, 2]
第 1 层（恰好 1 段），此时f全为 0：
j
新入队 k
窗口内最优 k
f[1][j]
1
k=0
0 → 0-0+4 = 4
4
2
k=1
0 → 0-0+5 = 5
max(4, 5) =5
3
k=2
0 → 0-0+0 = 0
max(5, 0) =5
4
k=3（值 0-0=0，弹出旧队尾）
3 → 0+2 = 2
max(5, 2) =5
第 1 层结束，f = [_, 4, 5, 5, 5]，ans = 5（只选一段时最优是[4,1]和为 5）。
第 2 层（恰好 2 段）：
j
新入队 k（值 = f[k]-s[k]）
队首贡献
f[2][j]
2
k=1（4-4=0）
0 + s[2]=5 → 5
5
3
k=2（5-5=0，弹出旧队尾 1）
0 + s[3]=0 → 0
max(5, 0) =5
4
k=3（5-0=5，弹出旧队尾 2）
5 + s[4]=2 →7
max(5, 7) =7
第 2 层结束，f[4] = 7，ans = max(5, 7) = 7。
最终返回7，对应方案：[4,1]（和 5）+[2]（和 2），两段长度分别为 2 和 1，都在 [1,3] 内，且不重叠。与题目给出的解释完全一致。
八、复杂度
时间复杂度：O(m · n)
• 前缀和预处理 O(n)；
• 外层 i 从 1 到 m，共 m 层；
• 第 i 层的 j 从
i×l扫到 n，最多 n 次；每次 j 的入队、查询、出队都是摊还 O(1)（每个 k 在一层内至多各进出队列一次）。• 合计 O(m · n)，再加上 O(n)，总复杂度O(m · n)，上界约 10⁶ 级别。相比朴素的 O(m · n · (r-l))，把"窗口扫描"这一维彻底消掉了。
额外空间复杂度：O(n)
• 前缀和数组
s：n+1；• 上一层 DP 数组
f：n+1；• 当前层 DP 数组
nf：n+1；• 单调队列
q：最坏情况下装下 n+1 个下标。
这些全都是 O(n) 量级，彼此是并列关系而非常数倍嵌套，所以总的额外空间是 O(n)（不含输入数组本身）。得益于滚动数组，原本 O(m·n) 的二维 DP 表被压成了两个一维数组。
Go完整代码如下：
package main
import (
"fmt"
"math"
)
func maximumSum(nums []int, m, left, right int) int64 {
n := len(nums)
s := make([]int, n+1) // nums 的前缀和
for i, x := range nums {
s[i+1] = s[i] + x
}
// f[i][j] 表示在前 j 个数（下标 0 到 j-1）中选出恰好 i 个子数组，所选元素之和的最大值
f := make([]int, n+1)
ans := math.MinInt
for i := 1; i <= m; i++ {
nf := make([]int, n+1)
for j := range nf {
nf[j] = math.MinInt / 2
}
q := []int{}
// 前 i 个子数组至少占用了 i * left 个位置
for j := i * left; j <= n; j++ {
// 1. 入
k := j - left
v := f[k] - s[k]
for len(q) > 0 && f[q[len(q)-1]]-s[q[len(q)-1]] <= v {
q = q[:len(q)-1]
}
q = append(q, k)
// 2. 更新
// 不选 nums[j-1] vs 选一个以 j-1 结尾的子数组
nf[j] = max(nf[j-1], f[q[0]]-s[q[0]]+s[j])
// 3. 出，下一轮循环队首离开窗口
if q[0] <= j-right {
q = q[1:]
}
}
// 枚举恰好选 i 个子数组
f = nf
ans = max(ans, f[n])
}
return int64(ans)
}func main() {
nums := []int{4, 1, -5, 2}
m := 2
l := 1
r := 3
result := maximumSum(nums, m, l, r)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from collections import deque
def maximum_sum(nums, m, left, right):
n = len(nums)
s = [0] * (n + 1) # 前缀和
for i, x in enumerate(nums):
s[i + 1] = s[i] + x
NEG = -10**30
# f[j] 表示在前 j 个数中选出恰好 i 个子数组时的最大总和
f = [0] * (n + 1)
ans = NEG
for i in range(1, m + 1):
nf = [NEG] * (n + 1)
q = deque()
# 前 i 个子数组至少需要 i * left 个位置
for j in range(i * left, n + 1):
# 入队：以 j-1 结尾、长度为 left 的子数组的起点
k = j - left
v = f[k] - s[k]
while q and f[q[-1]] - s[q[-1]] <= v:
q.pop()
q.append(k)
# 更新：不选 nums[j-1] 或选一个以 j-1 结尾的子数组
nf[j] = max(nf[j - 1], f[q[0]] - s[q[0]] + s[j])
# 出队：子数组长度不能超过 right
if q[0] <= j - right:
q.popleft()
f = nf
ans = max(ans, f[n])
return ansif __name__ == "__main__":
nums = [4, 1, -5, 2]
m = 2
l = 1
r = 3
result = maximum_sum(nums, m, l, r)
print(result)
C++完整代码如下：
using namespace std;
long long maximumSum(vector& nums, int m, int left, int right) {
int n = nums.size();
vector s(n + 1, 0); // 前缀和
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
const long long NEG = LLONG_MIN / 2;
// f[j] 表示在前 j 个数中选出恰好 i 个子数组时的最大总和
vector f(n + 1, 0);
long long ans = LLONG_MIN;
for (int i = 1; i <= m; ++i) {
vector nf(n + 1, NEG);
deque q;
// 前 i 个子数组至少需要 i * left 个位置
for (int j = i * left; j <= n; ++j) {
// 入队：以 j-1 结尾、长度为 left 的子数组的起点
int k = j - left;
long long v = f[k] - s[k];
while (!q.empty() && f[q.back()] - s[q.back()] <= v) {
q.pop_back();
}
q.push_back(k);
// 更新：不选 nums[j-1] 或选一个以 j-1 结尾的子数组
nf[j] = max(nf[j - 1], f[q.front()] - s[q.front()] + s[j]);
// 出队：子数组长度不能超过 right
if (q.front() <= j - right) {
q.pop_front();
}
}
f = nf;
ans = max(ans, f[n]);
}
return ans;
}int main() {
vector nums = {4, 1, -5, 2};
int m = 2;
int l = 1;
int r = 3;
long long result = maximumSum(nums, m, l, r);
cout << result << endl;
return 0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
