2026-09-16：M 个非重叠子数组最大和Ⅱ。用go语言，数组 nums 中共有 n 个整数，同时还给出了三个整数 m、l、r。现在需要从 nums 中取出|调用|下标|key|bool|spiderlinebreak

分享至

2026-09-16：M 个非重叠子数组最大和Ⅱ。用go语言，数组 nums 中共有 n 个整数，同时还给出了三个整数 m、l、r。现在需要从 nums 中取出若干个连续片段。取出的片段数量不能少于 1，也不能多于 m。不同片段之间不能重叠，也就是同一个数组位置最多只能属于其中一个片段。每个被取出片段的长度都必须大于等于 l 且小于等于 r。对于每一种满足条件的取法，把所有选中片段里的元素相加，得到一个总和。请找出所有合法取法中能够得到的最大总和并返回。这里的连续片段，指的是数组中一段连续且不为空的元素。

1 <= n == nums.length <= 100000。

-100000 <= nums[i] <= 100000。

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 个子数组下能够取得的最大总和。

题目来自力扣3957。

一、总体策略：三层套娃

这道题要求「至多 m 段、每段长度在 [l, r]、互不重叠、最大化元素和」。直接按段数做 DP 是O(n·m)，n 和 m 都能到 1e5，会炸。

代码用的是经典的三层结构：

干什么

复杂度

内层dpWithoutLimit(k)

先扔掉 m 这个限制

，但规定「每选一段就罚 k 分」，求最优

O(n)

中层

罚 0 分（k=0）时如果最优解本来就 ≤ m 段，直接返回

O(n)

外层

否则二分罚金 k，找到「刚好把段数压到 ≤ m」的那个最小 k，再还原真实答案

O(log P) 次调用内层

外层这一手就是常说的WQS 二分（带权二分 / 拉格朗日松弛 / Aliens Trick）。

二、预处理

1.前缀和s[i] = nums[0]+...+nums[i-1]，于是任意子数组nums[j..i-1]的和就是s[i] - s[j]，O(1) 得到。长度条件l ≤ i-j ≤ r等价于j ∈ [i-r, i-l]。
2.posSum：nums 中所有正数之和。它有两个用处——任意合法取法的总和都 ≤ posSum（因为负数只会拉低总和），所以它既是二分的上界，也是「罚金取到 posSum 就一定只选 1 段」的依据。

三、内层：固定罚金 k 的 DP 3.1 状态定义

f[i]是一个二元组(value, cnt)，表示「只在前i个元素nums[0..i-1]里做选择」能得到的最优结果：

•value= 选中元素之和减去k × 选中的段数（被"罚"之后的净得分）
•cnt= 该最优解用了几段

初始f[0] = (0, 0)（一个都不选），并且对i < l天然也是(0,0)——不足 l 个元素塞不进任何一段。

3.2 转移

对i ≥ l，只有两种可能：

1.不选以i-1结尾的段：f[i] = f[i-1]
2.选一段nums[j..i-1]结尾，其中j ∈ [i-r, i-l]：

• 新价值 =f[j].value + (s[i] - s[j]) - k=(f[j].value - s[j]) + s[i] - k
• 新段数 =f[j].cnt + 1

两者取更优的那个。

注意j那个位置允许前面一段都没选（f[j] = (0,0)），这正是"从 j 重新开始第一段"的情形，所以 DP 不需要额外的"起点"维度。

3.3 为什么要带 cnt 这个第二关键字

less(a, b)的语义是「a 严格劣于 b」，判定规则：

•a.value < b.value→ a 劣；
• 价值相等时，a.cnt > b.cnt→ a 劣（同分时段数越少越好）。

之所以要"同分少段优先"，有两个理由：

1. 惩罚项k·cnt本身就在鼓励少选段，同分少段正是我们想要的代表元；
2. 外层二分要判断「最优解段数是否 ≤ m」，取的既然是最少段数的最优解，一旦它 ≤ m，就说明"存在一个 ≤ m 段的最优解"，判定成立；同时它也让 k=0 那个快速分支尽可能命中。

四、单调队列把 O(n·r) 压成 O(n)

看转移里的关键项：对固定的i，s[i] - k是常数，所以要在j ∈ [i-r, i-l]里最大化的是

key(j) = f[j].value - s[j]（同 key 再比 cnt）

这是一个滑动窗口最大值问题：随着 i 从 l 走到 n，窗口[i-r, i-l]整体右移，每个 j 进一次出一次。代码用一个双端队列q维护"按优劣排好序的候选 j"，队首永远是当前窗口里最优的 j。

每一轮 i 做三件事（顺序很关键）：

1.入队：把新进入窗口的j = i-l加进来。加入前先把队尾那些劣于它的元素全部弹出——它们既比新元素差、又比新元素更早过期，永远不可能再成为队首，可以安全丢弃。于是队列从队首到队尾是"由优到劣"的单调序列。
2.查询：用队首q[0]算出「以 i 结尾选一段」的最优候选choose，拿它更新全局答案res，再和f[i-1]比较后写入f[i]。
3.出队：若q[0] <= i-r，说明它在下一轮就不在窗口里了，弹出。每轮最多弹一个，因为每轮窗口只滑一格。

每个 j 恰好入队一次、出队一次，所以单次dpWithoutLimit是O(n)。

五、resf为什么要分开

•f允许"一段都不选"（(0,0)分），这是 DP 能"中途重新开始"的前提。当所有选择都是亏的（净分为负），f[i]会保持(0,0)。
• 但题目要求至少选 1 段，所以另设res，初始化为-∞，且只在"以某处结尾真的选了一段"的候选里取最大。这样res.cnt ≥ 1恒成立，返回的才是合法解。

六、k = 0：能直接返回就别折腾

先算res0 = dpWithoutLimit(0)，即完全不惩罚时的最优总和无上界段数解。

• 不罚分时的最优值，是任何合法取法总和的上界；
• 如果它用的段数res0.cnt ≤ m，那它本身就是合法解，上界可达 → 直接返回res0.value。

样例[4,1,-5,2], m=2, l=1, r=3就走这条路（见第八节手推），直接出 7。

七、外层：WQS 二分找"刚刚好"的罚金

若res0.cnt > m，说明不限制段数时会忍不住多选，必须靠罚金来"劝退"。

7.1 单调性

罚金 k 越大，多开一段越不划算，最优解的段数cnt(k)单调不增。于是判定函数cnt(k) ≤ m呈「假…假真…真」的形态，可以二分找最小的满足条件的 k。

7.2 二分区间 [1, posSum]

• 下界 1：k=0 已经失败了。
• 上界 P = posSum 一定成功：任何取法的总和都 ≤ P，所以选 c 段的净分 ≤P - c·P。而进入二分说明数组里至少有一个正数，单段最大和h(1) ≥ 1，c=1 时净分 ≥1 - P，严格大于 c≥2 时的上界P - 2P = -P。故 k=P 时最优解只选 1 段，必然 ≤ m。（另外，若 posSum = 0，即全是非正数，那么"不罚分最优"一定是选 1 段，根本进不了这个分支，所以区间不会退化成空。）

代码用sort.Search(posSum, func(k int) bool { k++; ... })：搜索下标 0..P-1，闭包里k++把它映射成 k = 1..P，返回第一个为真的位置。

7.3 由"罚分后的值"还原"真实总和"

设在找到的最小 k 处，内层给出的结果是(F, c*)，即F = h(c*) - k·c*且c* ≤ m（h(c) 表示"恰好 c 段"的最大和）。答案是：

ans = F + m·k

为什么？

•上界方向（对任意 c ≤ m 都成立）：h(c) = (h(c) - k·c) + k·c ≤ F + k·m，因为h(c) - k·c不超过全局最优净分 F，且c ≤ m。所以真实答案一定 ≤F + m·k。
•可达方向：k 是"段数刚好被压到 ≤ m"的临界罚金，在这个临界点上，最优解族里一定存在一个恰好 m 段的解（k 再小 1 就会想选 > m 段，k 到此又已经不必少于 m 段）。对那个 m 段解有h(m) - k·m = F，即h(m) = F + m·k。

两边夹住，F + m·k就是"至多 m 段"的真实最大和——也就是把 m 段的罚金原样加回去。

八、样例手推：[4,1,-5,2], m=2, l=1, r=3

前缀和s = [0, 4, 5, 0, 2]，posSum = 7。跑dpWithoutLimit(0)（k=0）：

入队 j（key=f[j]-s[j], cnt）

队内情况

队首算出的 choose

res

f[i]

j=0 (0, 0)

0 + 4 =4, cnt=1

(4,1)

j=1 (4-4=0, 1)

[0,1]（j=0 同为 key=0 但 cnt 更小，留队首）

0 + 5 =5, cnt=1

(5,1)

j=2 (5-5=0, 1)

[0,1,2]

0 + s[3]=0 → 0, cnt=1

仍 (5,1)

(5,1)；弹出 j=0（0 ≤ 3-3）→ [1,2]

j=3 (5-0=5, 1)，弹出 j=2、j=1（key=0 < 5）

5 + 2 =7, cnt=2

(7,2)

最后res0 = (7, 2)，cnt = 2 ≤ m = 2→ 直接返回7。对应选法[4,1]与[2]，与题目解释完全一致。

九、复杂度

记n = len(nums)，P = posSum（所有正数之和，≤ n × 10^5 ≤ 10^10）。

时间复杂度：O(n log P)

• 预处理前缀和、posSum：O(n)
• 单次dpWithoutLimit：O(n)（单调队列均摊，每个下标入队出队各一次）
• 二分次数：外层sort.Search在 [1, P] 上二分，共O(log P)次；P ≤ 10^10 时约 34 次
• 合计O(n log P)，约 3.4×10^6 量级，n=1e5 完全可接受

额外空间复杂度：O(n)

• 前缀和数组s：n+1
• 每次调用的 DP 数组f：n+1（二分每轮重建，峰值仍是 n+1）
• 单调队列：窗口大小至多r-l+1 ≤ n
• 其余为常数

三者都是 O(n)。（补充一句实现细节：元素和最大可到 10^10，所以最终答案用int64返回；中间的前缀和、DP 值也需要在 64 位环境下才不会溢出。）

十、几个容易踩坑的点（小结）

1.队列里比较的是f[j].value - s[j]，不是f[j].value——因为对同一个 i，s[i] - k是公共项，提出来后才能用滑动窗口最值。
2.入队时机是j = i-l、出队条件是q[0] <= i-r，且出队放在查询之后，这样窗口才精确等于[i-r, i-l]（l == r 时也自洽）。
3.队列里存的是下标 j 而不是值——因为f[j]在 j 入队时已经算完、不会再变，但出队要靠下标和窗口边界比较。
4.f允许空选择、res不允许——分工解决了"至少选一段"的约束。
5.同分时段数少更优——既符合惩罚项的语义，也让二分的判定和还原干净利落。
6. 二分上界用 posSum 而不是 n 或 1e5——它是"任意取法的总和上限"，保证 k=P 时最优只剩 1 段。

Go完整代码如下：

package main

 import (
"fmt"
"math"
"sort"
)

 type pair struct{ f, cnt int } // DP 值, 子数组个数

 // 相等的时候，子数组个数更大的劣
func less(a, b pair)bool {
return a.f < b.f || a.f == b.f && a.cnt > b.cnt
}

 func maximumSum(nums []int, m, l, r int)int64 {
    n := len(nums)
    s := make([]int, n+1) // nums 的前缀和
    posSum := 0// nums 中的正数之和
for i, x := range nums {
        s[i+1] = s[i] + x
if x > 0 {
            posSum += x
        }
    }

 // 没有 m 约束，但每选一个子数组就要把元素和减少 k
    dpWithoutLimit := func(k int) pair {
        f := make([]pair, n+1)
        q := []int{}
        res := pair{math.MinInt, 0}

 for i := l; i <= n; i++ {
// 1. 入
            j := i - l
            v := pair{f[j].f - s[j], f[j].cnt}
forlen(q) > 0 && less(pair{f[q[len(q)-1]].f - s[q[len(q)-1]], f[q[len(q)-1]].cnt}, v) {
                q = q[:len(q)-1]
            }
            q = append(q, j)

 // 2. 更新答案
            choose := pair{f[q[0]].f - s[q[0]] + s[i] - k, f[q[0]].cnt + 1}
if less(res, choose) {
// choose 保证我们至少选了一个子数组
                res = choose
            }

 // 更新 DP
if less(f[i-1], choose) {
                f[i] = choose
            } else { // 不选
                f[i] = f[i-1]
            }

 // 3. 出，下一轮循环队首离开窗口
if q[0] <= i-r {
                q = q[1:]
            }
        }

 return res
    }

     res0 := dpWithoutLimit(0)
if res0.cnt <= m { // 直接满足题目要求
returnint64(res0.f)
    }

 // 现在专注于解决「选恰好 m 个子数组」的问题
    ans := 0
    sort.Search(posSum, func(k int)bool {
        k++
        res := dpWithoutLimit(k)
if res.cnt <= m {
            ans = res.f + m*k // 见题解【细节 1】
returntrue
        }
returnfalse
    })
returnint64(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 maximumSum(nums, m, l, r):
    n = len(nums)

     # 前缀和
    s = [0] * (n + 1)
    pos_sum = 0
for i, x in enumerate(nums):
        s[i + 1] = s[i] + x
if x > 0:
            pos_sum += x

     NEG_INF = -10**30

     # a 比 b 差：值更小，或者值相同但子数组个数更多
    def less(a, b):
return a[0] < b[0] or (a[0] == b[0] and a[1] > b[1])

     # 没有 m 约束，但每选一个子数组就减去惩罚 k
    def dp_without_limit(k):
        # f[i] = (最大收益, 使用的子数组个数)
        f = [(0, 0)] * (n + 1)
        q = deque()
        res = (NEG_INF, 0)

 for i in range(l, n + 1):
            # 1. 入队
            j = i - l
            v = (f[j][0] - s[j], f[j][1])

             while q:
                tail = q[-1]
                tail_val = (f[tail][0] - s[tail], f[tail][1])
if less(tail_val, v):
                    q.pop()
else:
break
            q.append(j)

             # 2. 更新答案
            q0 = q[0]
            choose = (f[q0][0] - s[q0] + s[i] - k, f[q0][1] + 1)

 if less(res, choose):
                res = choose

             # 更新 DP
if less(f[i - 1], choose):
                f[i] = choose
else:
                f[i] = f[i - 1]

             # 3. 出队，下一轮队首离开窗口
if q[0] <= i - r:
                q.popleft()

 return res

     # 先看没有 m 约束时的最优解
    res0 = dp_without_limit(0)
if res0[1] <= m:
return res0[0]

     # 用二分惩罚 k，解决「恰好 m 个子数组」的问题
    ans = 0
    lo, hi = 1, pos_sum
    while lo <= hi:
        mid = (lo + hi) // 2
        res = dp_without_limit(mid)

 if res[1] <= m:
            ans = res[0] + m * mid
            hi = mid - 1
else:
            lo = mid + 1

 return ans

 if __name__ == "__main__":
    nums = [4, 1, -5, 2]
    m = 2
    l = 1
    r = 3
print(maximumSum(nums, m, l, r))

C++完整代码如下：

  

  

  

    

  


 using namespace std;

 struct Node {
    long long f; // DP 值
int cnt;     // 子数组个数
};

 // f 更小，或 f 相等但子数组更多，则更劣
bool lessNode(const Node& a, const Node& b) {
return a.f < b.f || (a.f == b.f && a.cnt > b.cnt);
}

 int64_t maximumSum(const vector& nums, int m, int l, int r) {
int n = nums.size();

     vector 
 
 s(n +  
 1, 0); // 前缀和
    long long posSum = 0;          // 所有正数之和

 for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + nums[i];
if (nums[i] > 0) {
            posSum += nums[i];
        }
    }

 // 不限制子数组个数，但每选一个子数组要减去 k
    auto dpWithoutLimit = [&](long long k) -> Node {
        vector 
 
 dp(n +  
 1, {0, 0});
        deque q;

         Node res{numeric_limits 
 
 ::lowest(),  
 0};

 for (int i = l; i <= n; i++) {
// 1. 入队：j 是当前子数组的起点
int j = i - l;
            Node v{dp[j].f - s[j], dp[j].cnt};

             while (!q.empty()) {
int last = q.back();
                Node lastValue{dp[last].f - s[last], dp[last].cnt};

 if (!lessNode(lastValue, v)) {
break;
                }
                q.pop_back();
            }
            q.push_back(j);

 // 2. 选择一个以 i-1 结尾的子数组
int bestJ = q.front();
            Node choose{
                dp[bestJ].f - s[bestJ] + s[i] - k,
                dp[bestJ].cnt + 1
            };

 if (lessNode(res, choose)) {
                res = choose;
            }

 // 更新 DP：选择当前子数组，或者不选
if (lessNode(dp[i - 1], choose)) {
                dp[i] = choose;
            } else {
                dp[i] = dp[i - 1];
            }

 // 3. 出队：保证子数组长度不超过 r
if (!q.empty() && q.front() <= i - r) {
                q.pop_front();
            }
        }

 return res;
    };

     Node res0 = dpWithoutLimit(0);

 // 不限制子数组数量时，已经满足最多选 m 个
if (res0.cnt <= m) {
return res0.f;
    }

 // 二分查找惩罚值 k
    long long left = 1, right = posSum;
    long long ans = 0;

     while (left <= right) {
        long long mid = left + (right - left) / 2;
        Node res = dpWithoutLimit(mid);

 if (res.cnt <= m) {
            ans = res.f + 1LL * m * mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

 return ans;
}

 int main() {
    vector nums = {4, 1, -5, 2};
int m = 2;
int l = 1;
int r = 3;

     int64_t result = maximumSum(nums, m, l, r);
    cout << result << endl;

 return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的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.