社区讨论

本题解释

BBing37
P1121环状最大两段子段和参与者 10已保存回复 9

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@mjdq3yzo
此快照首次捕获于
2025/12/20 11:13
2 个月前
此快照最后确认于
2025/12/21 20:55
2 个月前
查看原帖
*step1：前情提要

本题主要考察动态Dp，枚举，数据结构（线性）*

动态Dp：

动态 DP（Dynamic Dynamic Programming）介绍

动态 DP 是一种 结合线段树（或平衡树）与动态规划 的高级算法，主要用于解决 带修改的动态规划问题。

核心场景

当传统 DP 面临以下情况时，动态 DP 是最优解法：

问题满足 DP 性质，但 状态会被动态修改（如点权 / 边权更新）；

每次修改后需要快速重新计算 DP 结果（单次修改 + 查询需接近对数时间）；

状态转移可以表示为 矩阵乘法 或 线性变换 形式（核心前提）。

核心思想

状态线性化：将 DP 转移方程转化为矩阵乘法（或类似的线性组合形式），利用矩阵乘法的结合律；

数据结构优化：用线段树维护区间内的转移矩阵乘积，实现区间合并与单点修改；

动态维护：修改时更新对应位置的转移矩阵，查询时通过线段树合并区间矩阵，快速得到 DP 结果。

关键性质

转移矩阵需满足 结合律（才能通过线段树合并）；

矩阵乘法定义可自定义（不一定是标准矩阵乘法，只要满足结合律即可）。

动态Dp be like:

CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

// 自定义2x2最大化矩阵
struct Matrix {
    ll mat[2][2];
    Matrix() { memset(mat, -0x3f, sizeof(mat)); }
    // 矩阵乘法：a * b，结果[i][j] = max(a[i][k] + b[k][j]) (k=0,1)
    friend Matrix operator*(const Matrix &a, const Matrix &b) {
        Matrix res;
        for (int i = 0; i < 2; ++i) {
            for (int k = 0; k < 2; ++k) {
                if (a.mat[i][k] == -INF) continue;
                for (int j = 0; j < 2; ++j) {
                    res.mat[i][j] = max(res.mat[i][j], a.mat[i][k] + b.mat[k][j]);
                }
            }
        }
        return res;
    }
};

const int N = 1e5 + 10;
vector<int> g[N];  // 树的邻接表
int n, m;
ll a[N];  // 节点权值

// 重链剖分相关数组
int fa[N], dep[N], sz[N], son[N];  // 父节点、深度、子树大小、重儿子
int top[N], id[N], rk[N], cnt;     // 链顶、dfs序、dfs序对应的节点、计数器

// 线段树：维护区间矩阵乘积
struct SegmentTree {
    int l, r;
    Matrix val;
} tr[N << 2];

// 重链剖分：第一遍dfs求fa, dep, sz, son
void dfs1(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    sz[u] = 1;
    for (int v : g[u]) {
        if (v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}

// 重链剖分：第二遍dfs求top, id, rk
void dfs2(int u, int t) {
    top[u] = t;
    id[u] = ++cnt;
    rk[cnt] = u;
    if (!son[u]) return;
    dfs2(son[u], t);  // 重儿子继承链顶
    for (int v : g[u]) {
        if (v != fa[u] && v != son[u]) {
            dfs2(v, v);  // 轻儿子新建链
        }
    }
}

// 初始化节点u的矩阵
Matrix init_mat(int u) {
    Matrix res;
    res.mat[0][0] = 0; res.mat[0][1] = 0;  // f[u][0] = max(...) + max(f[v][0], f[v][1])
    res.mat[1][0] = a[u]; res.mat[1][1] = -INF;  // f[u][1] = a[u] + f[v][0]
    return res;
}

// 线段树建树
void build(int p, int l, int r) {
    tr[p].l = l;
    tr[p].r = r;
    if (l == r) {
        tr[p].val = init_mat(rk[l]);
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    tr[p].val = tr[p << 1].val * tr[p << 1 | 1].val;
}

// 线段树单点更新（pos为dfs序）
void update(int p, int pos) {
    if (tr[p].l == tr[p].r) {
        tr[p].val = init_mat(rk[pos]);
        return;
    }
    int mid = (tr[p].l + tr[p].r) >> 1;
    if (pos <= mid) update(p << 1, pos);
    else update(p << 1 | 1, pos);
    tr[p].val = tr[p << 1].val * tr[p << 1 | 1].val;
}

// 线段树区间查询（l, r为dfs序）
Matrix query(int p, int l, int r) {
    if (tr[p].l >= l && tr[p].r <= r) return tr[p].val;
    int mid = (tr[p].l + tr[p].r) >> 1;
    Matrix res;
    // 单位矩阵初始化（乘法单位元：A * I = A）
    res.mat[0][0] = res.mat[1][1] = 0;
    res.mat[0][1] = res.mat[1][0] = -INF;
    if (l <= mid) res = res * query(p << 1, l, r);
    if (r > mid) res = res * query(p << 1 | 1, l, r);
    return res;
}

// 查询以u为根的子树的DP结果（通过链顶跳转合并矩阵）
Matrix query_chain(int u) {
    Matrix res;
    // 单位矩阵初始化
    res.mat[0][0] = res.mat[1][1] = 0;
    res.mat[0][1] = res.mat[1][0] = -INF;
    while (u) {
        res = res * query(1, id[top[u]], id[u]);  // 合并当前链
        u = fa[top[u]];  // 跳转到上一条链的链顶
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // 重链剖分
    dfs1(1, 0);
    dfs2(1, 1);
    // 建树
    build(1, 1, n);
    // 处理操作
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {  // 修改：u -> v
            int u, v;
            cin >> u >> v;
            a[u] = v;
            update(1, id[u]);
        } else {  // 查询最大权独立集
            Matrix ans = query_chain(1);
            cout << max(ans.mat[0][0], ans.mat[1][0]) << '\n';
        }
    }
    return 0;
}
PYTHON
import sys
from sys import stdin
sys.setrecursionlimit(1 << 25)  # 扩大递归限制（仅辅助，实际用迭代 DFS）

INF = 10**18

# 自定义2x2最大化矩阵（适配DP转移）
class Matrix:
    def __init__(self):
        self.mat = [[-INF] * 2 for _ in range(2)]
    
    # 矩阵乘法：self * other，满足结合律
    def __mul__(self, other):
        res = Matrix()
        for i in range(2):
            for k in range(2):
                if self.mat[i][k] == -INF:
                    continue
                for j in range(2):
                    if other.mat[k][j] == -INF:
                        continue
                    res.mat[i][j] = max(res.mat[i][j], self.mat[i][k] + other.mat[k][j])
        return res
    
    # 单位矩阵（乘法单位元：A * I = A）
    @staticmethod
    def identity():
        res = Matrix()
        res.mat[0][0] = 0
        res.mat[1][1] = 0
        return res

class DynamicDP:
    def __init__(self, n, a, edges):
        self.n = n
        self.a = a  # 节点权值（1-based）
        self.g = [[] for _ in range(n+1)]  # 邻接表
        for u, v in edges:
            self.g[u].append(v)
            self.g[v].append(u)
        
        # 重链剖分相关数组（1-based）
        self.fa = [0]*(n+1)    # 父节点
        self.dep = [0]*(n+1)   # 深度
        self.sz = [0]*(n+1)    # 子树大小
        self.son = [0]*(n+1)   # 重儿子
        self.top = [0]*(n+1)   # 链顶
        self.id = [0]*(n+1)    # 节点对应的dfs序
        self.rk = [0]*(n+1)    # dfs序对应的节点
        self.cnt = 0           # dfs序计数器
        
        # 线段树相关（大小为4*n，存储Matrix）
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [Matrix() for _ in range(2 * self.size)]
        
        # 初始化：重链剖分 + 建树
        self.dfs1_iter(1)  # 迭代版dfs1求fa/dep/sz/son
        self.dfs2_iter(1)  # 迭代版dfs2求top/id/rk
        self.build()
    
    # 迭代版dfs1：求fa, dep, sz, son
    def dfs1_iter(self, root):
        stack = [(root, 0, False)]
        while stack:
            u, f, visited = stack.pop()
            if visited:
                self.sz[u] = 1
                max_sz = 0
                for v in self.g[u]:
                    if v == f:
                        continue
                    self.sz[u] += self.sz[v]
                    if self.sz[v] > max_sz:
                        max_sz = self.sz[v]
                        self.son[u] = v
            else:
                self.fa[u] = f
                self.dep[u] = self.dep[f] + 1
                stack.append((u, f, True))
                # 逆序入栈，保证儿子处理顺序与递归一致
                for v in reversed(self.g[u]):
                    if v != f:
                        stack.append((v, u, False))
    
    # 迭代版dfs2：求top, id, rk
    def dfs2_iter(self, root):
        stack = [(root, root)]
        while stack:
            u, t = stack.pop()
            self.top[u] = t
            self.cnt += 1
            self.id[u] = self.cnt
            self.rk[self.cnt] = u
            # 重儿子先入栈（保证dfs序连续）
            has_son = False
            for v in reversed(self.g[u]):
                if v == self.fa[u]:
                    continue
                if v == self.son[u]:
                    stack.append((v, t))
                    has_son = True
                else:
                    stack.append((v, v))
    
    # 初始化单个节点的转移矩阵
    def init_mat(self, u):
        mat = Matrix()
        # f[u][0] = max(...) + max(f[v][0], f[v][1]) → 对应矩阵[0][0]和[0][1]
        mat.mat[0][0] = 0
        mat.mat[0][1] = 0
        # f[u][1] = a[u] + f[v][0] → 对应矩阵[1][0]，[1][1]不可取（设为-INF）
        mat.mat[1][0] = self.a[u-1]  # a是0-based输入，节点是1-based
        mat.mat[1][1] = -INF
        return mat
    
    # 建树（线段树）
    def build(self):
        # 叶子节点初始化
        for i in range(1, self.n+1):
            pos = self.size + self.id[i] - 1  # 线段树叶子节点位置（从size开始）
            self.tree[pos] = self.init_mat(self.rk[i])
        # 非叶子节点合并
        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.tree[2*i] * self.tree[2*i+1]
    
    # 单点更新（修改节点u的权值为v）
    def update(self, u, v):
        self.a[u-1] = v  # 更新权值
        pos = self.size + self.id[u] - 1  # 找到线段树中对应的叶子节点
        self.tree[pos] = self.init_mat(u)
        # 向上合并
        i = pos >> 1
        while i >= 1:
            new_mat = self.tree[2*i] * self.tree[2*i+1]
            if self.tree[i].mat == new_mat.mat:
                break  # 矩阵无变化，无需继续更新
            self.tree[i] = new_mat
            i >>= 1
    
    # 线段树区间查询（[l, r]为dfs序的闭区间）
    def query_interval(self, l, r):
        res = Matrix.identity()  # 初始为单位矩阵
        l += self.size - 1  # 转换为线段树叶子节点索引
        r += self.size - 1
        while l <= r:
            if l % 2 == 1:
                res = res * self.tree[l]
                l += 1
            if r % 2 == 0:
                res = res * self.tree[r]
                r -= 1
            l >>= 1
            r >>= 1
        return res
    
    # 链查询：查询从u到根的链的矩阵乘积
    def query_chain(self, u):
        res = Matrix.identity()
        while u != 0:
            # 合并当前链（top[u]到u的区间）
            res = res * self.query_interval(self.id[self.top[u]], self.id[u])
            u = self.fa[self.top[u]]  # 跳转到上一条链的链顶
        return res
    
    # 主查询：整棵树的最大权独立集
    def get_max_independent_set(self):
        mat = self.query_chain(1)  # 根节点为1
        return max(mat.mat[0][0], mat.mat[1][0])

def main():
    input = stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    m = int(input[ptr])
    ptr += 1
    a = list(map(int, input[ptr:ptr+n]))
    ptr += n
    edges = []
    for _ in range(n-1):
        u = int(input[ptr])
        ptr += 1
        v = int(input[ptr])
        ptr += 1
        edges.append((u, v))
    
    # 初始化动态DP
    dp = DynamicDP(n, a, edges)
    
    # 处理操作
    for _ in range(m):
        op = int(input[ptr])
        ptr += 1
        if op == 1:
            # 修改操作：u -> v
            u = int(input[ptr])
            ptr += 1
            v = int(input[ptr])
            ptr += 1
            dp.update(u, v)
        else:
            # 查询操作：输出最大权独立集
            print(dp.get_max_independent_set())

if __name__ == "__main__":
    main()

数据结构

线性数据结构是指数据元素之间仅存在 一对一的线性关系 的结构，即除首尾元素外，每个元素有且仅有一个前驱和一个后继。核心特点是 存储顺序与逻辑顺序一致，支持高效的遍历、插入、删除等操作，是算法与编程的基础。

常见的线性数据结构包括：数组、链表、栈、队列、双端队列、字符串，以下逐一介绍其定义、特性、核心操作及双语言实现。

CPP
#include <iostream>
using namespace std;

// 链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    // 构造函数
    ListNode(int x) : val(x), next(nullptr) {}
};

// 单链表类
class LinkedList {
private:
    ListNode* head;  // 头节点（哨兵节点，简化操作）
public:
    LinkedList() { head = new ListNode(0); }

    // 尾部插入
    void push_back(int x) {
        ListNode* cur = head;
        while (cur->next != nullptr) cur = cur->next;
        cur->next = new ListNode(x);
    }

    // 中间插入（在第index个元素后插入，index从0开始）
    void insert(int index, int x) {
        ListNode* cur = head;
        for (int i = 0; i < index && cur != nullptr; ++i) cur = cur->next;
        if (cur == nullptr) return;
        ListNode* new_node = new ListNode(x);
        new_node->next = cur->next;
        cur->next = new_node;
    }

    // 删除第index个元素（index从0开始）
    void erase(int index) {
        ListNode* cur = head;
        for (int i = 0; i < index && cur->next != nullptr; ++i) cur = cur->next;
        if (cur->next == nullptr) return;
        ListNode* temp = cur->next;
        cur->next = cur->next->next;
        delete temp;  // 释放内存
    }

    // 遍历
    void traverse() {
        ListNode* cur = head->next;
        while (cur != nullptr) {
            cout << cur->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }

    ~LinkedList() {
        // 析构函数，释放所有节点
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* temp = cur;
            cur = cur->next;
            delete temp;
        }
    }
};

int main() {
    LinkedList list;
    list.push_back(1);
    list.push_back(2);
    list.insert(1, 3);  // 在1后插入3 → 1 3 2
    list.erase(0);  // 删除第一个元素（1）→ 3 2
    list.traverse();  // 输出：3 2
    return 0;
}
PYTHON
# 链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 单链表类
class LinkedList:
    def __init__(self):
        self.head = ListNode()  # 哨兵头节点

    # 尾部插入
    def push_back(self, x):
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = ListNode(x)

    # 中间插入（在第index个元素后插入）
    def insert(self, index, x):
        cur = self.head
        for _ in range(index):
            if not cur:
                return
            cur = cur.next
        if not cur:
            return
        new_node = ListNode(x)
        new_node.next = cur.next
        cur.next = new_node

    # 删除第index个元素
    def erase(self, index):
        cur = self.head
        for _ in range(index):
            if not cur.next:
                return
            cur = cur.next
        if not cur.next:
            return
        cur.next = cur.next.next

    # 遍历
    def traverse(self):
        res = []
        cur = self.head.next
        while cur:
            res.append(cur.val)
            cur = cur.next
        print("链表遍历：", res)

# 测试
list = LinkedList()
list.push_back(1)
list.push_back(2)
list.insert(1, 3)
list.erase(0)
list.traverse()  # 输出：[3, 2]

*枚举算法（也称穷举算法）是最基础、最直观的算法思想：通过逐一列举所有可能的解，并对每个解进行验证，最终找到符合条件的解（或所有解）。

其核心逻辑：

确定问题的解空间（所有可能的候选解范围）；

遍历解空间中的每个候选解；

对每个候选解验证是否满足问题的约束条件；

收集所有满足条件的候选解作为最终结果。

二、适用场景

解空间规模较小（避免遍历耗时过长）；

问题的约束条件清晰明确（便于验证候选解）；

没有更高效的算法（如贪心、动态规划）可用时的 “兜底方案”。

常见例子：

密码破解（遍历所有可能的密码组合）；

查找范围内的素数（遍历每个数验证是否为素数）；

百钱买百鸡问题（遍历鸡的数量组合验证条件）；

组合求和（遍历所有组合验证和是否符合要求）。

三、优缺点

优点

逻辑简单，易于理解和实现；

只要解空间存在解，枚举算法一定能找到（完备性）；

适用于约束条件复杂的问题（无需推导复杂逻辑，只需验证条件）。

缺点

效率低下：解空间越大，遍历时间越长（时间复杂度通常为 O (n)、O (n²) 等，取决于解空间维度）；

浪费资源：会遍历大量无效解，尤其当解空间庞大时（如枚举 10 位密码，解空间为 10¹⁰，完全不可行）。*```cpp

CPP
#include <iostream>
#include <cmath>
using namespace std;

// 验证一个数是否为素数
bool isPrime(int num) {
    if (num <= 1) return false;  // 1及以下不是素数
    if (num == 2) return true;   // 2是最小素数
    if (num % 2 == 0) return false;  // 偶数（除2外）不是素数
    
    // 优化：只需遍历到 sqrt(num)（因数成对出现）
    for (int i = 3; i <= sqrt(num); i += 2) {
        if (num % i == 0) return false;
    }
    return true;
}

int main() {
    cout << "1~100 中的素数：" << endl;
    // 枚举解空间：1~100
    for (int i = 1; i <= 100; ++i) {
        if (isPrime(i)) {  // 验证候选解
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}
PYTHON
import math

def is_prime(num):
    if num <= 1:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False
    # 遍历到 sqrt(num)，步长为2（只查奇数）
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

# 枚举 1~100 的所有数，筛选素数
primes = [i for i in range(1, 101) if is_prime(i)]
print("1~100 中的素数：", primes)

本题思路

一、问题核心分析

关键约束

序列是环状（首尾相邻）；

选择连续、不重叠、非空的两段；

目标：两段和之和最大。

核心难点

环状结构增加了 “跨首尾” 的可能（如最后一段 + 第一段）；

两段不能重叠，且必须连续；

数据规模 n≤2×10⁵，要求算法时间复杂度≤O (n)（O (n²) 会超时）。

CPP
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    vector<long long> left_max(n);
    left_max[0] = a[0];
    long long current = a[0];
    for (int i = 1; i < n; ++i) {
        current = max((long long)a[i], current + a[i]);
        left_max[i] = max(left_max[i-1], current);
    }

    vector<long long> right_max(n);
    right_max[n-1] = a[n-1];
    current = a[n-1];
    for (int i = n-2; i >= 0; --i) {
        current = max((long long)a[i], current + a[i]);
        right_max[i] = max(right_max[i+1], current);
    }

    long long max_sum = LLONG_MIN;
    for (int i = 0; i < n-1; ++i) {
        max_sum = max(max_sum, left_max[i] + right_max[i+1]);
    }
    cout << max_sum << endl;
    return 0;
}
PYTHON
n = int(input())
a = list(map(int, input().split()))

# 预处理前缀最大子段和、后缀最大子段和
left_max = [0] * n
left_max[0] = current = a[0]
for i in range(1, n):
    current = max(a[i], current + a[i])
    left_max[i] = max(left_max[i-1], current)

right_max = [0] * n
right_max[-1] = current = a[-1]
for i in range(n-2, -1, -1):
    current = max(a[i], current + a[i])
    right_max[i] = max(right_max[i+1], current)

# 只计算不跨首尾的情况
max_sum = -float('inf')
for i in range(n-1):
    max_sum = max(max_sum, left_max[i] + right_max[i+1])

print(max_sum)

*错误类型 2：未限制中间子段长度，导致某一段为空

思路

计算「跨首尾」情况时，直接用 total - 整个序列的最小子段和，未保证中间子段长度 ≤n-2，可能导致两段中有一段为空。*

PYTHON
total = sum(a)
# 错误：最小子段可能是整个序列（长度n），导致两段为空
min_sub = float('inf')
current_min = 0
for num in a:
    current_min = min(num, current_min + num)
    min_sub = min(min_sub, current_min)
case2 = total - min_sub  # 可能无效
超时类型 1：暴力枚举两段的起始和结束位置 思路 枚举第一段的 [i,j] 和第二段的 [k,l]，验证不重叠后计算和，时间复杂度 O (n³)，即使 n=1e3 也超时。
CPP
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

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

    long long max_sum = LLONG_MIN;
    // 枚举第一段 [i,j]
    for (int i = 0; i < n; ++i) {
        long long sum1 = 0;
        for (int j = i; j < n; ++j) {
            sum1 += a[j];
            // 第二段在右侧 [k,l]
            long long sum2 = 0;
            for (int k = j+1; k < n; ++k) {
                sum2 += a[k];
                if (sum1 + sum2 > max_sum) max_sum = sum1 + sum2;
            }
            // 第二段在左侧 [l,i-1]
            sum2 = 0;
            for (int l = i-1; l >= 0; --l) {
                sum2 += a[l];
                if (sum1 + sum2 > max_sum) max_sum = sum1 + sum2;
            }
        }
    }
    cout << max_sum << endl;
    return 0;
}
PYTHON
n = int(input())
a = list(map(int, input().split()))
max_sum = -float('inf')

# 枚举第一段 [i,j]
for i in range(n):
    sum1 = 0
    for j in range(i, n):
        sum1 += a[j]
        # 枚举第二段在第一段右侧 [k,l]
        sum2 = 0
        for k in range(j+1, n):
            sum2 += a[k]
            if sum1 + sum2 > max_sum:
                max_sum = sum1 + sum2
        # 枚举第二段在第一段左侧（环状）[l,i-1]
        sum2 = 0
        for l in range(i-1, -1, -1):
            sum2 += a[l]
            if sum1 + sum2 > max_sum:
                max_sum = sum1 + sum2

print(max_sum)
用前缀和数组快速计算子段和，枚举分割点后，分别计算左侧最大子段和与右侧最大子段和，时间复杂度 O (n²)。
PYTHON
n = int(input())
a = list(map(int, input().split()))
prefix = [0]*(n+1)
for i in range(n):
    prefix[i+1] = prefix[i] + a[i]

max_sum = -float('inf')

# 枚举分割点 m（左侧0..m，右侧m+1..n-1）
for m in range(n-1):
    # 计算左侧0..m的最大子段和
    left_max = -float('inf')
    for i in range(m+1):
        for j in range(i, m+1):
            left_max = max(left_max, prefix[j+1] - prefix[i])
    # 计算右侧m+1..n-1的最大子段和
    right_max = -float('inf')
    for i in range(m+1, n):
        for j in range(i, n):
            right_max = max(right_max, prefix[j+1] - prefix[i])
    max_sum = max(max_sum, left_max + right_max)

# 处理跨首尾情况（单独枚举，仍O(n²)）
for m in range(1, n):
    # 左侧m..n-1的最大子段和
    left_max = -float('inf')
    for i in range(m, n):
        for j in range(i, n):
            left_max = max(left_max, prefix[j+1] - prefix[i])
    # 右侧0..m-1的最大子段和
    right_max = -float('inf')
    for i in range(m):
        for j in range(i, m):
            right_max = max(right_max, prefix[j+1] - prefix[i])
    max_sum = max(max_sum, left_max + right_max)

print(max_sum)
step3：正确代码
PYTHON
def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    a = list(map(int, input[1:n+1]))
    
    # 特殊情况：n=2 只能选两个单个元素
    if n == 2:
        print(a[0] + a[1])
        return
    
    total = sum(a)  # 序列总和（用于跨首尾情况）

    # -------------------------- 关键1：预处理4个核心数组（Kadane算法）--------------------------
    # 1. left_max[i]：a[0..i]的最大子段和
    left_max = [0] * n
    left_max[0] = current_max = a[0]
    for i in range(1, n):
        current_max = max(a[i], current_max + a[i])  # 延续子段或重新开始
        left_max[i] = max(left_max[i-1], current_max)  # 更新前缀最大

    # 2. right_max[i]：a[i..n-1]的最大子段和（从右往左算）
    right_max = [0] * n
    right_max[-1] = current_max = a[-1]
    for i in range(n-2, -1, -1):
        current_max = max(a[i], current_max + a[i])
        right_max[i] = max(right_max[i+1], current_max)

    # 3. left_min[i]：a[0..i]的最小子段和（用于跨首尾情况）
    left_min = [0] * n
    left_min[0] = current_min = a[0]
    for i in range(1, n):
        current_min = min(a[i], current_min + a[i])  # 延续子段或重新开始
        left_min[i] = min(left_min[i-1], current_min)  # 更新前缀最小

    # 4. right_min[i]：a[i..n-1]的最小子段和（从右往左算）
    right_min = [0] * n
    right_min[-1] = current_min = a[-1]
    for i in range(n-2, -1, -1):
        current_min = min(a[i], current_min + a[i])
        right_min[i] = min(right_min[i+1], current_min)

    # -------------------------- 关键2：计算两种情况的最大值 --------------------------
    # 情况1：不跨首尾（分割点i，左段0..i，右段i+1..n-1）
    case1 = -float('inf')
    for i in range(n-1):
        case1 = max(case1, left_max[i] + right_max[i+1])

    # 情况2：跨首尾（总和 - 中间最小子段和，中间子段长度≤n-2，保证两段非空）
    min_mid = min(left_min[n-2], right_min[1])  # 排除中间子段占满整个序列的情况
    case2 = total - min_mid

    # 最终答案：两种情况的最大值
    print(max(case1, case2))
CPP
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    // 关键0：输入优化（适配2e5数据量，避免IO超时）
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    long long total = 0;  // 关键：用long long防溢出（总和可达2e9）
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        total += a[i];
    }

    // 特殊情况：n=2 只能选两个单个元素
    if (n == 2) {
        cout << (long long)a[0] + a[1] << endl;
        return 0;
    }

    // -------------------------- 关键1：预处理4个核心数组（Kadane算法）--------------------------
    vector<long long> left_max(n);
    left_max[0] = a[0];
    long long current_max = a[0];
    for (int i = 1; i < n; ++i) {
        current_max = max((long long)a[i], current_max + a[i]);
        left_max[i] = max(left_max[i-1], current_max);
    }

    vector<long long> right_max(n);
    right_max[n-1] = a[n-1];
    current_max = a[n-1];
    for (int i = n-2; i >= 0; --i) {
        current_max = max((long long)a[i], current_max + a[i]);
        right_max[i] = max(right_max[i+1], current_max);
    }

    vector<long long> left_min(n);
    left_min[0] = a[0];
    long long current_min = a[0];
    for (int i = 1; i < n; ++i) {
        current_min = min((long long)a[i], current_min + a[i]);
        left_min[i] = min(left_min[i-1], current_min);
    }

    vector<long long> right_min(n);
    right_min[n-1] = a[n-1];
    current_min = a[n-1];
    for (int i = n-2; i >= 0; --i) {
        current_min = min((long long)a[i], current_min + a[i]);
        right_min[i] = min(right_min[i+1], current_min);
    }

    // -------------------------- 关键2：计算两种情况的最大值 --------------------------
    long long case1 = LLONG_MIN;
    for (int i = 0; i < n-1; ++i) {
        case1 = max(case1, left_max[i] + right_max[i+1]);
    }

    long long min_mid = min(left_min[n-2], right_min[1]);
    long long case2 = total - min_mid;

    cout << max(case1, case2) << endl;
    return 0;
}

上方代码若有问题请Dalao指出，蒟蒻必关注

回复

共 9 条回复，欢迎继续交流。

正在加载回复...