题解代码

状态机动态规划建模

本题可以看作是一个状态机 DP问题，每个下标 i 都有两种状态：

• 状态 $s_1(i)$：必须以下标 $i$ 结尾的子段最大和 即当前子段必须包含 $a_i$，对应 dp[i][1]。
• 状态 $s_0(i)$：前 $i$ 个元素中的全局最大子段和 表示截止到 $i$，我们看到的所有子段里，最大和是多少，对应 dp[i][0]。

把每个 $i$ 看作状态机的一个节点，节点上有两种状态（局部状态与全局状态），通过状态转移方程在下标之间“跳转”。

状态转移（Transition）

状态机的转移分为两类：

1. 局部状态转移 若我们必须以 $i$ 结尾，那么有两种选择：

   • 从上一个局部状态延续：$dp[i-1][1] + a_i$
   • 从当前位置重启：$a_i$

   因此：

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

2. 全局状态转移 全局最大值要么保持上一步的全局最优，要么更新为新的局部最大：

   $$dp[i][0] = \max(dp[i-1][0],\ dp[i][1])$$

这样，每次迭代就相当于驱动状态机从 $i-1$ 跳转到 $i$，同时更新两个状态值。

边界条件（Initial State）与答案

状态机初始时，必须以下标 1 结尾的子段最大和就是 $a_1$，全局最大子段和也是 $a_1$：

最终答案是处理完所有状态后，全局状态的值：

代码实现

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // dp[i][1]：必须以 i 结尾的子段最大和
    // dp[i][0]：前 i 个元素的全局最大子段和
    vector<array<long long, 2>> dp(n + 1);

    // 边界
    dp[1][1] = a[1];
    dp[1][0] = a[1];

    for (int i = 2; i <= n; ++i) {
        // 转移：以 i 结尾，要么续接，要么从 a[i] 重启
        dp[i][1] = max(dp[i - 1][1] + a[i], a[i]);
        // 维护全局
        dp[i][0] = max(dp[i - 1][0], dp[i][1]);
    }

    cout << dp[n][0] << "\n";
    return 0;
}

Python

import sys

data = sys.stdin.read().strip().split()
if not data:
    sys.exit(0)

it = iter(data)
n = int(next(it))
a = [0] * (n + 1)
for i in range(1, n + 1):
    a[i] = int(next(it))

# dp[i][1]：必须以 i 结尾的子段最大和
# dp[i][0]：前 i 个元素的全局最大子段和
dp1 = [0] * (n + 1)  # 对应 dp[i][1]
dp0 = [0] * (n + 1)  # 对应 dp[i][0]

# 边界
dp1[1] = a[1]
dp0[1] = a[1]

for i in range(2, n + 1):
    # 以 i 结尾：续接或重启
    dp1[i] = max(dp1[i - 1] + a[i], a[i])
    # 全局最优
    dp0[i] = max(dp0[i - 1], dp1[i])

print(dp0[n])

Java

import java.io.*;
import java.util.*;

public class Main {
    // 简单快读：跨多行读取所有整数
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= ' ' && c != -1);
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n;
        try { n = fs.nextInt(); } catch (Exception e) { return; }
        long[] a = new long[n + 1];
        for (int i = 1; i <= n; i++) a[i] = fs.nextInt();

        // dp[i][1]：必须以 i 结尾的子段最大和
        // dp[i][0]：前 i 个元素的全局最大子段和
        long[] dp1 = new long[n + 1]; // 对应 dp[i][1]
        long[] dp0 = new long[n + 1]; // 对应 dp[i][0]

        // 边界
        dp1[1] = a[1];
        dp0[1] = a[1];

        for (int i = 2; i <= n; i++) {
            // 以 i 结尾：续接或重启
            dp1[i] = Math.max(dp1[i - 1] + a[i], a[i]);
            // 全局最优
            dp0[i] = Math.max(dp0[i - 1], dp1[i]);
        }

        System.out.println(dp0[n]);
    }
}

题目描述：

给定一个整数序列 $a_1, a_2, \dots, a_n$，其中 $n$ 为整数序列的长度。请你计算出该序列的最大子段和，即从该序列中选出一个连续的子序列，使得子序列的和最大。请注意，子序列的长度可以为 1，且可以是整个序列。

输入：

输入的第一行包含一个整数 $n$ $(1 \leq n \leq 10^5)$，表示序列的长度。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(-10^4 \leq a_i \leq 10^4)$，表示序列中的元素。

输出：

输出一个整数，表示最大子段和。

样例输入：

9
-2 1 -3 4 -1 2 1 -5 4

样例输出：

6

提示：

在上面的例子中，最大子段和为 6，对应的子序列为 $[4, -1, 2, 1]$。