最大子段和的变种

普通最大子段和只要求连续、非空。增加长度或段数限制后，需要在原来的状态中保留这些限制。

以下所有子段均非空，多个子段互不重叠，但允许相邻。只求最大和，不要求输出方案。

一、长度至少为 $m$ 的最大子段和

设前缀和 $s[0]=0$，$s[i]=a[1]+\cdots+a[i]$。若子段为 $[j+1,i]$，其和为 $s[i]-s[j]$。

长度至少为 $m$，即 $i-j\ge m$，所以：

$$\text{以 }i\text{ 结尾的最优值}=s[i]-\min_{0\le j\le i-m}s[j]$$

从左往右枚举 $i$，合法的 $j$ 不断增加，只需维护一个前缀和最小值。

例如 2 -5 4 3 -1，$m=3$。枚举到 $i=5$ 时，最小的合法前缀和为 $s[2]=-3$，得到 $s[5]-s[2]=6$，对应子段 4 3 -1。

关键代码如下：

long long ans = LLONG_MIN, mn = 0;
for (int i = m; i <= n; ++i) {
    mn = min(mn, s[i - m]);
    ans = max(ans, s[i] - mn);
}

这里约定 $1\le m\le n$。每次先加入新合法位置 $i-m$，再计算答案，时间复杂度 $O(n)$。

二、长度至多为 $m$ 的最大子段和

同样约定 $1\le m\le n$，考虑子段 $[j+1,i]$。由 $1\le i-j\le m$，得到：

$$\max(0,i-m)\le j\le i-1$$

所以：

$$\text{以 }i\text{ 结尾的最优值} =s[i]-\min_{\max(0,i-m)\le j\le i-1}s[j]$$

与上一题相比，合法范围的左端点也在移动，旧的最小值可能过期，不能再只用一个变量维护。

使用单调队列保存前缀和的下标，使对应的前缀和从队头到队尾递增，队头就是当前范围内的最小值。

每次枚举右端点 $i$：删除过期下标，加入 $i-1$，再用队头更新答案。

int q[N], head = 1, tail = 0;
long long ans = LLONG_MIN;
for (int i = 1; i <= n; ++i) {
    while (head <= tail && q[head] < i - m) ++head;
    int j = i - 1;
    while (head <= tail && s[q[tail]] >= s[j]) --tail;
    q[++tail] = j;
    ans = max(ans, s[i] - s[q[head]]);
}

队尾已有的前缀和若不小于新值，就可以删除：新值更小或相等，而且下标更大、过期更晚。

例如 2 -5 4 3 -1，$m=2$。当 $i=4$ 时，候选下标为 $2,3$，取 $s[2]=-3$，得到子段 4 3，和为 $7$。

每个下标最多入队、出队各一次，时间复杂度 $O(n)$。只能加入 $i-1$，不能先加入 $i$，否则会把空子段算进去。

三、最大两段子段和

在线性序列中选择恰好两段互不重叠的非空子段，求总和最大值，约定 $n\ge2$。两段允许相邻。

两段之间一定能找到一个分界点：左段在 $[1,i]$ 中，右段在 $[i+1,n]$ 中。因此，分别求出：

• $l[i]$：前 $i$ 个数中的最大子段和。
• $r[i]$：从第 $i$ 个数到第 $n$ 个数中的最大子段和。

从左往右做一次普通最大子段和，再从右往左做一次，即可求出这两个数组。注意：$l[i]$、$r[i]$ 记录的是范围内的最优值，不要求子段紧贴分界点。

正向扫描时，用 cur 记录以当前位置结尾的最大子段和。先更新 cur = max(a[i], cur + a[i])，再更新 l[i] = max(l[i-1], cur)。

反向扫描时，cur 则记录以当前位置开头的最大子段和，转移形式相同，再更新 r[i] = max(r[i+1], cur)。

枚举分界点，答案为：

$$\max_{1\le i<n}\bigl(l[i]+r[i+1]\bigr)$$

固定分界点后，左右两侧可以独立选择最优子段；枚举所有分界点，就不会漏掉最优的两段。

例如 2 -5 4 3 -1：

下标 $i$	1	2	3	4	5
$a[i]$	2	-5	4	3	-1
$l[i]$		2		7
$r[i]$	7			3	-1

在 $i=2$ 处分开，得到 $l[2]+r[3]=2+7=9$，对应两段 2 和 4 3。

long long l[N], r[N];

long long cur = a[1];
l[1] = cur;
for (int i = 2; i <= n; ++i) {
    cur = max(a[i], cur + a[i]);
    l[i] = max(l[i - 1], cur);
}

cur = a[n];
r[n] = cur;
for (int i = n - 1; i >= 1; --i) {
    cur = max(a[i], cur + a[i]);
    r[i] = max(r[i + 1], cur);
}

long long ans = LLONG_MIN;
for (int i = 1; i < n; ++i) ans = max(ans, l[i] + r[i + 1]);

时间、空间复杂度均为 $O(n)$。初始化时使用实际元素，保证全负数时仍然选出两段；合并时使用 $r[i+1]$，保证两段不重叠。

四、环状最大两段子段和

将序列首尾相接，选择恰好两段互不重叠的非空连续段，求总和最大值。两段允许相邻，其中一段可以跨越首尾，约定 $n\ge2$。

按照常规断环成链来考虑，假定$a[n]$和$a[1]$之间的边断开，可以分为两种情况，如下图所示：

在 $a[n]$ 与 $a[1]$ 之间断开，分两种情况：

• 没有子段跨过断点：就是上一节的最大两段子段和。
• 有子段跨过断点：跨界段被拆成首、尾两部分，再加上另一段，在线性序列中表现为三段。
  第一种情况用最大两段子段和方法解决即可，第二中可以转化为总和-两段最小子段和的方法解决。

// 情况一：不跨界，求最大两段子段和
    long long cur = a[1];
    l[1] = cur;
    for (int i = 2; i <= n; ++i) {
        cur = max(a[i], cur + a[i]);
        l[i] = max(l[i - 1], cur);
    }

    cur = a[n];
    r[n] = cur;
    for (int i = n - 1; i >= 1; --i) {
        cur = max(a[i], cur + a[i]);
        r[i] = max(r[i + 1], cur);
    }

    long long ans = LLONG_MIN;
    for (int i = 1; i < n; ++i)     ans = max(ans, l[i] + r[i + 1]);


    // 情况二：跨界，总和减去两段最小子段和
    // 重新计算 l、r，未选部分允许为空
    l[1] = 0;
    cur = 0;
    for (int i = 2; i < n; ++i) {
        cur = min(0LL, cur + a[i]);
        l[i] = min(l[i - 1], cur);
    }

    r[n] = 0;
    cur = 0;
    for (int i = n - 1; i >= 2; --i) {
        cur = min(0LL, cur + a[i]);
        r[i] = min(r[i + 1], cur);
    }

    // 保留位置 i，保证另一段非空
    for (int i = 2; i < n; ++i)     ans = max(ans, s[n] - l[i - 1] - r[i + 1]);

五、最大 $k$ 段子段和

在线性序列中选择恰好 $k$ 段互不重叠的非空子段，求总和最大值，约定 $1\le k\le n$。

1. 先枚举上一段的结尾

定义 $dp[i][j]$：恰好选了 $j$ 段，且 $a[i]$ 作为第 $j$ 段结尾时，所有已选子段的最大总和。

考虑 $a[i]$ 如何加入方案：

• 接在第 $j$ 段后面：由 $dp[i-1][j]+a[i]$ 转移。
• 以 $a[i]$ 新开第 $j$ 段：枚举前 $j-1$ 段的最后一个位置 $t<i$，由 $dp[t][j-1]+a[i]$ 转移。

这里用 $t$ 表示枚举位置，避免与题目要求的段数 $k$ 混淆。因此：

$$dp[i][j]=\max\left(dp[i-1][j]+a[i],\ \max_{j-1\le t<i}\{dp[t][j-1]+a[i]\}\right)$$

初始化 $dp[0][0]=0$，表示还没有选任何数，其余状态为 $-\infty$。当 $j=1$ 时，取 $t=0$ 就表示从 $a[i]$ 开始第一段。

答案为 $\max_{k\le i\le n}dp[i][k]$，因为最后一段不一定在 $n$ 结束。

下面的 dp 为二维数组，仅适合小规模数据，需预留足够的行数与列数。用 memset(dp, 0x80, sizeof(dp)) 将数组初始化为极小的负数，在本题范围内作为负无穷：

memset(dp, 0x80, sizeof(dp));
dp[0][0] = 0;

for (int i = 1; i <= n; ++i) 
    for (int j = 1; j <= min(i, k); ++j) {
        dp[i][j] = dp[i - 1][j] + a[i];
        for (int t = j - 1; t < i; ++t) 
            dp[i][j] = max(dp[i][j], dp[t][j - 1] + a[i]);
    }

long long ans = dp[k][k];
for (int i = k; i <= n; ++i) ans = max(ans, dp[i][k]);

共有 $O(nk)$ 个状态，每次枚举上一段的结尾需要 $O(n)$，总时间复杂度为 $O(n^2k)$。

2. 用前缀最大值优化

观察新开一段的转移：

$$\max_{j-1\le t<i}dp[t][j-1]+a[i]$$

$a[i]$ 与 $t$ 无关，真正需要的只是 $dp[t][j-1]$ 在前 $i-1$ 个位置中的最大值，不必每次重新枚举。

定义 $best[i][j]$ 为前 $i$ 个位置中，恰好选 $j$ 段的最大总和，即 $dp[\,\cdot\,][j]$ 的前缀最大值：

$$best[i][j]=\max\bigl(best[i-1][j],\ dp[i][j]\bigr)$$

于是转移变为：

$$dp[i][j]=\max\bigl(dp[i-1][j],\ best[i-1][j-1]\bigr)+a[i]$$

初始化 $best[i][0]=0$，其余状态为 $-\infty$。每个状态只需 $O(1)$ 转移，时间复杂度降为 $O(nk)$，答案就是 $best[n][k]$。

例如 2 -5 4 3 -1，计算 $dp[4][2]$ 时，新开第二段需要枚举 $dp[1][1]$、$dp[2][1]$、$dp[3][1]$，它们分别为 $2,-3,4$。用 $best[3][1]=4$ 就能直接代替这次枚举。

3. 压缩空间后的核心代码

每一行只依赖上一行，将 dp、best 压缩为一维即可。段数倒序枚举，保证 best[j-1] 仍是上一位置的值，避免重复使用 $a[i]$。

long long dp[N], best[N];

memset(dp, 0x80, sizeof(dp));
memset(best, 0x80, sizeof(best));
best[0] = 0;

for (int i = 1; i <= n; ++i) {
    for (int j = min(i, k); j >= 1; --j) {
        dp[j] = max(dp[j], best[j - 1]) + a[i];
        best[j] = max(best[j], dp[j]);
    }
}
long long ans = best[k];

只需保存 $k+1$ 个状态，所需状态空间为 $O(k)$；这里用容量为 N 的静态数组存储。注意要求恰好 $k$ 段，不能把所有状态初始化为 $0$，否则全负数时会少选段数。