什么是「最大子段和」

给一串数 $a_1,a_2,\dots,a_n$ （可正可负），子段是原序列里连续的一段 $a_l,a_{l+1},\dots,a_r$ —— 注意和「子序列」不同，子段必须挨着取、不能跳。我们要找的，是所有子段里和最大的那一段（一般要求非空，至少含一个数）。

序列 −2, 11, −4, 13, −5, −2：柱高即数值（正上负下）。高亮的连续一段 11,−4,13 之和为 20，是最大子段——中间那个 −4 虽是负数，但为了连起两侧的大正数，值得含进来。

盯住上图那段 $11,-4,13$ ：它跨过了一个负数 $-4$ ，可总和 $11-4+13=20$ 仍是最优。这就是难点所在——要不要把当前这个数接进来，取决于前面攒下的和是正是负：前面若攒了正的一坨（如 $11-4=7$ ），哪怕眼下遇到 $13$ 也该接上去滚成 $20$ ；可前面若攒成了负数，那这负担就该果断丢掉、从当前数重新起一段。

最笨的办法是枚举左右端点 $l,r$ 再累加，那是 $O(n^3)$ ；加前缀和也要 $O(n^2)$ 。当 $n=2\times10^5$ ，这些都会超时。下面用一个只扫一遍的 DP——Kadane 算法——把它压到 $O(n)$ 。

状态与转移：接续，还是另起

沿用 LIS 那把母题抓手：最大子段落在哪儿事先不知道，与其对「全局最优段」直接设状态，不如钉住它的结尾。设 $dp[i]$ 表示：以 $a_i$ 为最后一个元素的最大子段和。于是 $n$ 个不同结尾把所有候选段分门别类地兜住，一个也不漏、一个也不重。

每个 dp[i] 只有两条路：把 a[i] 接在前一段后面（dp[i−1]+a[i]），或让它自己另起一段（a[i]）。谁大取谁。

怎么算 $dp[i]$ ？既然它以 $a_i$ 结尾，那 $a_i$ 左边紧挨着的那段，只有两种可能：

接续：把 $a_i$ 接在「以 $a_{i-1}$ 结尾的最优段」后面，得 $dp[i-1]+a_i$ 。

另起：前面那段是负担（ $dp[i-1]<0$ ），干脆扔掉，让 $a_i$ 自己单独成一段，得 $a_i$ 。

两条路取较大，就是转移方程：

dp[i]=\max\big(dp[i-1]+a_i,\ a_i\big)

边界： $dp[1]=a_1$ （第一个数只能自成一段）。答案不是 $dp[n]$ ——因为最大子段可在任何位置收尾——而是整个 $dp$ 数组的最大值：

\text{ans}=\max_{1\le i\le n}dp[i]

本质

「以 $a_i$ 结尾」这个限定，把「求全局最大子段」拆成了 $n$ 个可顺序递推的小问题。转移只回看一格 $dp[i-1]$ ，于是一趟 $O(n)$ 扫描就够，连数组都能省成一个滚动变量。★答案取全行最大，且全为负数时 $\text{ans}$ 初值必须设成 $a_1$ 而非 $0$ ，否则会误答 0。

跟着算一遍

用序列 $a=[-2,11,-4,13,-5,-2]$ 走几步（下标从 1 记），把方程跑起来：

0

起点。

dp[1]=a_1=-2

（第一个数只能自成一段）。当前全局最大

\text{ans}=-2

。

1

到 11。 接续

dp[1]+11=-2+11=9

，另起

11

。另起更大（前面

-2

是负担）→

dp[2]=11

，

\text{ans}=11

。

2

到 −4。 接续

11+(-4)=7

，另起

-4

。接续更大 →

dp[3]=7

（含住这个负数，赌后面有更大的正数）。

\text{ans}

仍

11

。

3

到 13。 接续

7+13=20

，另起

13

。接续更大 →

dp[4]=20

。赌赢了——刷新

\text{ans}=20

，正是那段

11,-4,13

。

4

剩下 −5、−2。

dp[5]=\max(20-5,-5)=15

，

dp[6]=\max(15-2,-2)=13

，都没超过

20

。扫完，答案 20。

下面的演示把

dp[]

逐格填出来，并高亮每一步「接续（连回

dp[i-1]

）还是另起」的抉择。改数组、加删元素，或换个预设看它实时重算。

看它一格一格长出来

最大子段和 = dp[] 的全局最大值：20

0

1

2

3

4

5

a

dp

-2

11

-4

13

-5

-2

·

当前计算依赖来源被选转移已确定

dp[i]=\max(dp[i-1]+a_i,\ a_i)

上排是原数组 a[]（只读参照），下排 dp[i] 表示「以 a[i] 结尾的最大子段和」。每一步在接续与另起之间取较大者。

进度

已暂停，第 1 步，共 8 步，1 倍速

深化 · 环形：断环与补集

换个设定：这串数首尾相接成一个环，子段可以跨过末尾绕回开头（例如 $a_{n-1},a_n,a_1,a_2$ 是合法的一段）。最大子段和又该怎么求？

分两种情况。其一，最优段不跨首尾——那它就是普通的一段，直接跑一遍上面的 Kadane 即可。其二，最优段跨过了首尾——这时它由「结尾的一截」和「开头的一截」拼成，绕过了中间某一段。关键一步是反着看：一个「绕首尾的段」和它「中间被绕过的那段」正好互补，两者拼起来是整个环。记 $\text{total}=\sum a_i$ ，则「绕首尾的最大段」等于总和减去中间被绕过的那段：

\text{wrap}=\text{total}-\text{minSeg}

要让绕首尾的段最大，就要让中间挖掉的那段最小——而这个 $\text{minSeg}$ （最小子段和）把 Kadane 里的 $\max$ 换成 $\min$ 就能一趟求出。最终答案取两种情况的较大者：

\text{ans}=\max\big(\text{maxSeg},\ \text{total}-\text{minSeg}\big)

环形 2,−1,2,−1,2：普通 Kadane 全取得 4；但绕过中间的最小子段 −1（total − minSeg = 4 − (−1) = 5）更优——最优段跨过了首尾。

常见陷阱 · 全正数会绕整圈

用 $\text{total}-\text{minSeg}$ 时，若数组全为正数，最小子段会退化成「最小的单个元素」， $\text{total}-\text{minSeg}$ 相当于「几乎绕整整一圈」，把同一个环重复计入——非法。稳妥写法：仅当最小子段没有吃掉整个数组（还留下至少一个元素）时才采用补集；实践中若普通 Kadane 的结果已 $\ge0$ ，直接取两者较大即可自然避开这个坑。

下面把两种算法并排跑给你看：左边普通 Kadane 求「不跨首尾」的最大段，右边把

\max

换成

\min

求最小子段、再用

\text{total}-\text{minSeg}

求「绕首尾」的段。改数值看谁胜出。

普通 Kadane 4 · 环形（total − minSeg = 4 − (-1)） 5 · 取较大 → 答案 5（最优段跨过首尾，补集技巧胜出）

普通 Kadane · 不跨首尾的最大子段

0

1

2

3

4

a

dp

2

-1

2

-1

2

·

当前计算依赖来源被选转移已确定

dp[i]=\max(dp[i-1]+a_i,\ a_i)

上排是原数组 a[]（只读参照），下排 dp[i] 表示「以 a[i] 结尾的最大子段和」。每一步在接续与另起之间取较大者。

进度

已暂停，第 1 步，共 7 步，1 倍速

环形补集 · 求最小子段，再 total − minSeg

0

1

2

3

4

a

mn

2

-1

2

-1

2

·

当前计算依赖来源被选转移已确定

mn[i]=\min(mn[i-1]+a_i,\ a_i)

同一套 Kadane，只把 max 换成 min：mn[i] 是「以 a[i] 结尾的最小子段和」。

进度

已暂停，第 1 步，共 7 步，1 倍速

例题

P1115最大子段和洛谷原生普及-

题意

给定长度

n

的整数序列（含负数），求最大子段和（连续、非空的一段）。

为什么选它

最裸的 Kadane 模板，

n\le 2\times10^5

逼你放弃

O(n^2)

前缀和暴力、写出一趟

O(n)

的「接续 vs 另起」——把这套状态设计写熟，一个滚动变量就够。

转移 · 复杂度

dp=\max(dp+a_i,\ a_i)

，答案

\max_i dp_i

；时间

O(n)

，空间

O(1)

。★

\text{ans}

初值取

a_1

，防全负误答 0。

参考代码（滚动变量 Kadane）

C++

在洛谷打开 P1115

#include <algorithm>
#include <iostream>
using namespace std;

int n, a;
int dp, ans;                     // dp：以当前数结尾的最大子段和；ans：全局最大

int main()
{
    cin >> n;
    cin >> a;
    dp = a;                          // 第一个数：只能自成一段
    ans = a;                         // ★ans 初值设成 a[1]，别设 0（全负时会错）
    for (int i = 2; i <= n; i++)
    {
        cin >> a;
        dp = max(dp + a, a);         // 接续 dp+a 还是另起 a，取较大
        ans = max(ans, dp);          // 子段可在任意位置结尾，随时刷新全局最大
    }

    cout << ans << endl;
    return 0;
}
// TAG: 线性DP 最大子段和 Kadane

P2642双子序列最大和洛谷原生普及+/提高

题意

在序列中选两段不相交、非空的子段，使两段和最大。求这个最大值。

为什么选它

把「两段不相交」单独练透，是环形题 P1121 的台阶。核心套路是前后缀最优拼接：正向求「前缀内最大子段」

bp[i]

、反向求「后缀内最大子段」

bs[i]

，再枚举被跳过的中间数

i

，让左段取

bp[i-1]

、右段取

bs[i+1]

各据一侧——这是一大类「拆成互不相交若干段」问题的通法。

转移 · 复杂度

pre/suf

各跑一遍 Kadane，

bp/bs

做前后缀最大；答案

\max_{2\le i<n}(bp[i{-}1]+bs[i{+}1])

（枚举被跳过的中间数

i

，保证两段隔开）；时间

O(n)

。

参考代码（前后缀最优拼接）

C++

在洛谷打开 P2642

#include <algorithm>
#include <iostream>
using namespace std;

const int MX = 1000005;
long long a[MX];
long long pre[MX], suf[MX];      // pre[i]：以 i 结尾的最大子段；suf[i]：以 i 开头的最大子段
long long bp[MX], bs[MX];        // bp[i]：前缀 [1..i] 里的最大子段；bs[i]：后缀 [i..n] 里的最大子段

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    pre[1] = a[1];
    for (int i = 2; i <= n; i++)                 // 正向 Kadane，落成「以 i 结尾」
    {
        pre[i] = max(pre[i - 1] + a[i], a[i]);
    }
    bp[1] = pre[1];
    for (int i = 2; i <= n; i++)                 // 前缀最大子段（可结尾于 ≤ i 处）
    {
        bp[i] = max(bp[i - 1], pre[i]);
    }

    suf[n] = a[n];
    for (int i = n - 1; i >= 1; i--)             // 反向 Kadane，落成「以 i 开头」
    {
        suf[i] = max(suf[i + 1] + a[i], a[i]);
    }
    bs[n] = suf[n];
    for (int i = n - 1; i >= 1; i--)             // 后缀最大子段（可开头于 ≥ i 处）
    {
        bs[i] = max(bs[i + 1], suf[i]);
    }

    long long ans = -0x3f3f3f3f3f3f3f3f;
    for (int i = 2; i < n; i++)                  // 枚举被跳过的中间数 i：左段收尾于 ≤ i-1，右段起于 ≥ i+1
    {
        ans = max(ans, bp[i - 1] + bs[i + 1]);   // 两段不相交且至少隔开中间的 i，各取自己那侧的最大
    }

    cout << ans << endl;
    return 0;
}
// TAG: 线性DP 最大子段和 两段不相交 前后缀

P1121环状最大两段子段和洛谷原生提高+/省选-

题意

序列首尾相接成环，选两段不相交、非空的子段（可跨首尾），求两段和最大。

为什么选它

一题同时叠环形与两段不相交两个变形，是本类集大成。核心是「恰好 K 段不相交」DP（

f[j]

=已选

j

段的最大和、

g[j]

=第

j

段延伸到当前位）加上一层补集：情况一两段都不跨首尾，直接在

a

上求最大两段；情况二有段跨首尾，剩下的绕首尾两段等于「总和减去中间挖掉的最小两段」，而中间的最小两段又等于「在

-a

上求最大两段」再取负。讲透「用补集绕开环」。

转移 · 复杂度

kmax(b,K)

对

j

逆序更新

g[j]=\max(f[j-1],g[j])+b_i,\ f[j]=\max(f[j],g[j])

；两种情况各调一次（第二种在掐头去尾的

-a[2..n-1]

上），取较大，时间

O(nK)

。★情况二必须给首尾各留至少一个元素，别让挖掉的两段吃光整环。

参考代码（恰好 K 段 DP + 补集）

C++

在洛谷打开 P1121

#include <algorithm>
#include <iostream>
using namespace std;

const int MX = 200005;
const long long INF = 0x3f3f3f3f3f3f3f3f;
int n;
long long a[MX], tot;

// 序列 b[l..r] 里选「恰好 K 段不相交、非空」子段的最大总和。
// f[j]=已选 j 段的最大和；g[j]=已选 j 段且第 j 段延伸到当前位的最大和。
long long kmax(long long b[], int l, int r, int K)
{
    long long f[3], g[3];
    for (int j = 0; j <= K; j++)
    {
        f[j] = -INF, g[j] = -INF;
    }
    f[0] = 0;
    for (int i = l; i <= r; i++)
    {
        for (int j = K; j >= 1; j--)             // ★逆序 j，防第 j 段在本轮被重复计入
        {
            g[j] = max(f[j - 1], g[j]) + b[i];   // 新开一段 或 延续第 j 段
            f[j] = max(f[j], g[j]);
        }
    }
    return f[K];
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        tot += a[i];
    }

    // 情况一：两段都不跨首尾 —— 序列 a[1..n] 上直接选最大两段。
    long long ans = kmax(a, 1, n, 2);

    // 情况二：有段跨首尾 —— 剩下的绕首尾两段 = 总和 − (中间挖掉的最小两段)。
    // 挖掉的两段必须落在「掐头去尾」的 a[2..n−1] 内，才能把环切成两段弧（首尾各留 ≥1）。
    // 最小两段 = −(在 −a 上的最大两段)，故 ans 候选 = tot + kmax(−a, 2..n−1, 2)。
    if (n >= 4)                                  // 内层至少 2 个元素才能挖两段
    {
        for (int i = 1; i <= n; i++)
        {
            a[i] = -a[i];
        }
        ans = max(ans, tot + kmax(a, 2, n - 1, 2));
    }

    cout << ans << endl;
    return 0;
}
// TAG: 线性DP 环状最大两段子段和 K段DP 补集

练习

P1719最大加权矩形二维压一维：枚举上下边界两行，把这两行之间每列求和压成一维数组，问题就退化成对这一维做一次最大子段和（Kadane）。外层枚举 O(n²) 对行界，内层 O(m) 跑 Kadane。在洛谷打开

P2642双子序列最大和（回炉自测）上面精讲过的「两段不相交」——先合上参考代码，自己独立把前后缀 bp[]/bs[] 推一遍再枚举分界；吃透它，环形的 P1121 就只是再叠一层补集。在洛谷打开

小字说明：最大子段和的洛谷原生练习池偏窄（多数同类题是本页例题本身）。除上面两题外，建议把例题 P1121 / P2642 当自测——先合上参考代码独立写、再对照，是巩固「环形 / 两段不相交」最有效的方式。