切蛋糕

GitHub跳转原题关系图返回列表

把限长子段和写成前缀和之差，用单调队列维护最近 m 个前缀和的最小值。

OJ: luogu

题目 ID: P1714

难度:普及

标签:前缀和单调队列python

创建: 2025-12-26 19:34

更新: 2026-10-07 12:15

前置题目
luogu P2251质量检测B 把 A 教的滑窗最小值单调队列原样套在前缀和数组上，用当前前缀减窗口最小前缀得限长最大子段和luogu P1886【模板】单调队列 / 滑动窗口B 的限长最大子段和直接复用 A 的「单调队列维护滑动窗口最值、删过期队头后队头即答案」这一步，只是队列里存的是前缀和并以当前前缀减窗口最小前缀得到答案luogu P2032扫描先掌握单调队列维护滑动窗口最值。
后置题目
luogu P2216[HAOI2007] 理想的正方形B 把 A 教的单调队列窗口最值原语在横、纵两个方向各套一遍求正方形内最值差，A 的前缀和换法只是它的一个应用luogu P2627[USACO11OPEN] Mowing the Lawn GB 的转移 dp[i]=S[i]+max(dp[j-1]-S[j]) 复用 A 教的「递增单调队列维护滑窗内前缀式最值、先删过期队头再算答案」这一步，只是队列里存的量从前缀和换成 dp[j-1]-S[j] 并由求最小换成求最大luogu P2629好消息，坏消息先掌握前缀和 + 单调队列求滑动窗口最小值，再处理断环成链 + 窗口验证的组合。luogu P1725琪露诺B 的转移优化复用 A 教的「单调队列维护滑动窗口最值、先删除过期队头再加入新候选」这一步（dp[i]=A[i]+max(dp[j]) 的窗口最值就靠它），再叠加 A 未教的跳跃模型与「答案可从 i+R>N 直接跳出」的非固定终点处理。luogu P1419寻找段落B 的二分答案检验把均值判定化成 b[i]=a[i]-est 后，逐 i 取 [i-T,i-S] 窗口内最小前缀做 S[i]-min 判定，直接复用 A 教的「单调队列取滑动窗口最小前缀和」这一步，外面再套二分答案与数组平移。
相似题目
luogu P2032扫描同为单调队列维护滑动窗口的应用。

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

选择长度在 1..m1..m 之间的非空连续子段，使元素和最大。

思路

设 prefix[i] 为前 ii 项和。固定右端前缀 i 时，合法左端前缀 j 位于 [i-m,i-1]，子段和是 prefix[i]-prefix[j]。因此只需维护这个滑动窗口内最小的前缀和。

递增单调队列保存候选前缀；先删除过期队头并计算答案，再把当前前缀作为未来候选加入。

Python 知识

  • 不保存完整前缀数组，只用变量 prefix 在线累加。
  • 两个紧凑数组分别保存候选下标与前缀值，适合五十万规模。
  • 流式整数解析同时支持负数并控制内存。

代码

python
import os
from array import array


def read_ints():
    number = 0
    sign = 1
    reading = False
    while chunk := os.read(0, 1 << 20):
        for byte in chunk:
            if 48 <= byte <= 57:
                number = number * 10 + byte - 48
                reading = True
            else:
                if reading:
                    yield sign * number
                    number = 0
                    sign = 1
                    reading = False
                elif byte == 45:
                    sign = -1
    if reading:
        yield sign * number


data = iter(read_ints())
n, limit = next(data), next(data)
queue_index = array("i", [0]) * (n + 1)
queue_value = array("q", [0]) * (n + 1)
head, tail = 0, 1
prefix = 0
answer = -10**30

for i in range(1, n + 1):
    prefix += next(data)
    while head < tail and queue_index[head] < i - limit:
        head += 1
    answer = max(answer, prefix - queue_value[head])
    while head < tail and queue_value[tail - 1] >= prefix:
        tail -= 1
    queue_index[tail] = i
    queue_value[tail] = prefix
    tail += 1

print(answer)

复杂度

时间复杂度 O(n)O(n)，空间复杂度 O(n)O(n)。

总结

限长最大子段和等价于“当前前缀减最近窗口内最小前缀”。