你好！很高兴看到你坚持不懈地推进到了第四题。

针对题目四：最多删除一次的最大子数组和（Max Sum with At Most One Deletion），这个题目的数据生成需要极强的**“剧情设计感”**。如果只用全随机数据，极大可能连续几个正数就把最大值刷出来了，根本测不出参赛者“是否正确实现了删除一次”的逻辑。

作为出题人，我们必须人为制造一些**“陷阱（Traps）”**：比如两块巨大的金矿（正数），中间隔着一条深不可测的鸿沟（极小的负数）。优秀的算法会毫不犹豫地使用删除特权跨过鸿沟，而有 Bug 的算法则会在这里摔得粉碎！

测试点梯度与覆盖策略设计

(注：单数据值范围控制在 $[-10000, 10000]$ 之间，最大的文件在 $600\text{KB}$ 左右，整套数据总计不到 $2\text{MB}$，极致轻量，极速生成。)

C++ 数据生成器代码 (data_maker_deletion.cpp)

请新建一个文件夹，将以下代码保存并编译运行。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

// 枚举数据生成的特殊模式
enum DataType {
    RANDOM_MIXED = 1, // 全随机混合
    ALL_POSITIVE,     // 全正数
    ALL_NEGATIVE,     // 全负数
    SINGLE_TRAP,      // 单点深渊
    DOUBLE_TRAP,      // 双重深渊 (防无限删除)
    FREQUENT_MINOR,   // 密集的微小负数
    ALTERNATING,      // 正负高频交替
    ADJACENT_TRAPS,   // 连续的深渊 (防连续删除)
    ONE_POSITIVE      // 仅有一个正数
};

// 采用 mt19937 高质量随机生成器，固定种子以保证数据一致性
mt19937 rng(4096); 

// 生成指定范围内的随机整数 [L, R]
int get_rand(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rng);
}

// 核心求解函数 (标准答案 O(N) 空间 O(1))
long long solve_correct_answer(const vector<int>& a) {
    if (a.empty()) return 0;
    
    long long no_del = a[0];
    long long one_del = -INF;
    long long global_max = a[0];

    for (size_t i = 1; i < a.size(); ++i) {
        long long val = a[i];
        
        long long prev_no_del = no_del;
        long long prev_one_del = one_del;

        no_del = max(val, prev_no_del + val);
        
        // 注意防止下溢出
        long long inherited = (prev_one_del == -INF) ? -INF : prev_one_del + val;
        one_del = max(prev_no_del, inherited);

        global_max = max({global_max, no_del, one_del});
    }

    return global_max;
}

// 按照不同剧情模式生成数组
vector<int> generate_array(int n, DataType type) {
    vector<int> a(n);
    switch (type) {
        case RANDOM_MIXED:
            for (int i = 0; i < n; ++i) a[i] = get_rand(-10000, 10000);
            break;
            
        case ALL_POSITIVE:
            for (int i = 0; i < n; ++i) a[i] = get_rand(1, 10000);
            break;
            
        case ALL_NEGATIVE:
            for (int i = 0; i < n; ++i) a[i] = get_rand(-10000, -1);
            break;
            
        case SINGLE_TRAP:
            for (int i = 0; i < n; ++i) a[i] = get_rand(100, 1000); // 都是正数
            a[n / 2] = -10000; // 在正中央安插一个极小负数，诱导算法删除
            break;
            
        case DOUBLE_TRAP:
            for (int i = 0; i < n; ++i) a[i] = get_rand(100, 1000);
            a[n / 3] = -10000;
            a[n * 2 / 3] = -10000;
            break;
            
        case FREQUENT_MINOR:
            for (int i = 0; i < n; ++i) {
                // 大量正数，夹杂偶尔的微小负数 (-1 到 -10)
                if (get_rand(1, 4) == 1) a[i] = get_rand(-10, -1);
                else a[i] = get_rand(100, 1000);
            }
            break;
            
        case ALTERNATING:
            for (int i = 0; i < n; ++i) {
                if (i % 2 == 0) a[i] = get_rand(100, 1000);
                else a[i] = get_rand(-10000, -1);
            }
            break;

        case ADJACENT_TRAPS:
            for (int i = 0; i < n; ++i) a[i] = get_rand(100, 1000);
            a[n / 2] = -10000;
            a[n / 2 + 1] = -10000; // 连续的坑，只能跨过一个，必定会断开
            break;

        case ONE_POSITIVE:
            for (int i = 0; i < n; ++i) a[i] = get_rand(-10000, -1);
            a[get_rand(0, n - 1)] = get_rand(1, 100);
            break;
    }
    return a;
}

// 生成单个测试点文件的全套流程
void generate_test_case(int test_id, int n, DataType type) {
    vector<int> a = generate_array(n, type);

    // --- 写入 .in 文件 ---
    string in_filename = to_string(test_id) + ".in";
    ofstream fin(in_filename);
    if (!fin) {
        cerr << "无法创建文件: " << in_filename << "\n";
        return;
    }
    fin << n << "\n";
    for (int i = 0; i < n; ++i) {
        fin << a[i] << (i == n - 1 ? "" : " ");
    }
    fin << "\n";
    fin.close();

    // --- 计算并写入 .out 文件 ---
    long long ans = solve_correct_answer(a);
    string out_filename = to_string(test_id) + ".out";
    ofstream fout(out_filename);
    if (!fout) {
        cerr << "无法创建文件: " << out_filename << "\n";
        return;
    }
    fout << ans << "\n";
    fout.close();

    cout << "Test Case " << test_id << " 成功生成. (N = " << n << ", 剧情模式 = " << type << ", 答案 = " << ans << ")\n";
}

int main() {
    // 提升流读写性能
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << "开始生成《最多删除一次的最大子数组和》测试数据...\n";

    // 梯度 1：小型数据与极端边界
    generate_test_case(1, 10, RANDOM_MIXED);
    generate_test_case(2, 50, ALL_POSITIVE);
    generate_test_case(3, 50, ALL_NEGATIVE); // 防非法空集必杀
    
    // 梯度 2：中型规模，用于卡 O(n^3)，并测试删除特权的准确度
    generate_test_case(4, 500, SINGLE_TRAP);
    generate_test_case(5, 5000, DOUBLE_TRAP); // 验证是否只删了1次
    
    // 梯度 3：大型边界构造，强制检验状态转移的鲁棒性
    generate_test_case(6, 10000, FREQUENT_MINOR);
    generate_test_case(7, 100000, ALTERNATING);
    generate_test_case(8, 100000, ONE_POSITIVE);
    generate_test_case(9, 100000, ADJACENT_TRAPS); // 防连续越野必杀
    
    // 梯度 4：综合极限盲测
    generate_test_case(10, 100000, RANDOM_MIXED);

    cout << "全部10组测试点生成完毕！\n";
    return 0;
}

👨‍🏫 教练的工程心得（出题人视角）：

1. “相邻深渊（Adjacent Traps）”的精妙之处： 在测试点 9（ADJACENT_TRAPS）中，我故意安排了两个紧挨着的 -10000。 有些同学的代码如果写错了状态机，变成了“遇到负数就贪心抛弃一次”，遇到两个连续负数时，可能会出现“虽然名义上只用了一次权限，但其实把两段正数连起来了”的 Bug（比如错用了双向指针）。在这个剧情里，因为特权只有一次，遇到两道深渊，优秀的算法会果断放弃相连，接受断裂，只取其中较大的一段加上跨过深渊的一点零头。
2. 防下溢出 Exception： 你可能会注意到，本题中如果在 $a[0]$ 阶段 one_del 就被置为了 -INF（$-10^{18}$），在后续循环里，如果不加判定直接 one_del + a[i]，在遇到巨大的负数时，极有可能会超出 long long 的下限（约 $-9 \times 10^{18}$），产生底层补码翻转变正数的离谱错误（Underflow）。我在 inherited = (prev_one_del == -INF) ? -INF : prev_one_del + val; 这句代码里加了强力的熔断保护，这就是专业竞赛选手护航程序的肌肉记忆。你出数据的时候也一定要考虑到这点！

你好！这节课我们来攻克题目四：最多删除一次的最大子数组和（Max Sum with At Most One Deletion）。

相比于基础的求和，这道题引入了**“一次修改权限”。这种带有“操作次数限制”的区间问题，在NOI/CSP考场上极具代表性，它考察的核心能力是“状态扩展（State Extension）”**——即如何给 DP 穿上“不同历史条件”的马甲。

为了让你吃透这个套路，我们依然从朴素的模拟开始，一步步推导到双状态的满分神仙解法。

版本一：朴素暴力枚举（时间 $O(n^3)$，空间 $O(n)$）

【思考过程】 既然允许“最多删除一次”，最暴力的想法自然是：

1. 枚举子数组的左端点 L。
2. 枚举子数组的右端点 R。
3. 算出不删除时的和。
4. 如果区间长度大于 1，枚举删掉里面的哪一个元素 k（$L \le k \le R$），并求出剩下的和。
5. 所有情况打擂台取最大值。

【竞赛评价】 这是极其纯粹的暴力，时间复杂度 $O(n^3)$。在 $N=10^5$ 时计算量达到 $10^{15}$，绝对会 TLE。但在比赛前 30 分钟毫无头绪时，写出它能帮你稳拿 20%~30% 的分数。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

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];
    }

    long long global_max = -INF;

    // 枚举左端点 L
    for (int L = 1; L <= n; ++L) {
        // 枚举右端点 R
        for (int R = L; R <= n; ++R) {
            
            // 1. 不删除任何元素的情况
            long long sum_no_del = 0;
            for (int k = L; k <= R; ++k) {
                sum_no_del += a[k];
            }
            global_max = max(global_max, sum_no_del);

            // 2. 尝试删除其中的某一个元素 k (区间长度 > 1 时才允许删除)
            if (R > L) {
                for (int skip = L; skip <= R; ++skip) {
                    long long sum_with_del = 0;
                    for (int k = L; k <= R; ++k) {
                        if (k != skip) { // 跳过指定的删除元素
                            sum_with_del += a[k];
                        }
                    }
                    global_max = max(global_max, sum_with_del);
                }
            }
        }
    }

    cout << global_max << "\n";
    return 0;
}

版本二：贪心优化暴力（时间 $O(n^2)$，空间 $O(n)$）

【时间复杂度优化建议】 在枚举 [L, R] 区间时，真的需要把里面的元素挨个删一遍来试吗？ 当然不需要！如果我们决定要删，一定要删掉这个区间里最小的那个元素（且必须是负数才值得删）。 所以我们可以在右边界 R 扩大的时候，同时维护一个当前区间的总和与最小值。 【竞赛评价】 通过简单的贪心观察，砍掉了一层循环，复杂度降为 $O(n^2)$。能通过 $N \le 5000$ 的数据，拿到大约 50~60 分。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

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];
    }

    long long global_max = -INF;

    for (int L = 1; L <= n; ++L) {
        long long current_sum = 0;
        long long min_val = INF; // 维护区间的最小值

        for (int R = L; R <= n; ++R) {
            current_sum += a[R];
            min_val = min(min_val, a[R]); // O(1) 更新最小值

            // 选择1：不删除
            global_max = max(global_max, current_sum);

            // 选择2：删除最小值（前提是区间至少有2个元素，保证删除后非空）
            if (R > L) {
                global_max = max(global_max, current_sum - min_val);
            }
        }
    }

    cout << global_max << "\n";
    return 0;
}

版本三：二维动态规划（时间 $O(n)$，空间 $O(n)$）—— 核心破局点

【复杂度分析与思考过程】 对于 $N=10^5$，我们必须做到 $O(n)$。使用“连续 DP”的黄金法则，我们尝试定义以第 $i$ 个数结尾的状态。 但这里有个问题：走到第 $i$ 个数时，之前的历史记录有没有用过“删除特权”？我们不得而知。 破局点：扩展状态维度（Add a flag）！ 我们开两个数组：

• dp0[i]：以 $i$ 结尾，0次删除的最大和。
• dp1[i]：以 $i$ 结尾，1次删除的最大和。

【状态转移推导】

1. dp0[i] 完全就是最基础的 Kadane 算法：max(a[i], dp0[i-1] + a[i])。
2. dp1[i] 怎么来？有两种途径到达“删了 1 次”的状态：
   • 路线 A（这一步刚刚被删）： 前面 $i-1$ 步都没删过，刚好把第 $i$ 个数字删了！那么它接上的包袱就是 dp0[i-1]。（注意：这种情况下，虽然名为以 $i$ 结尾，但 $a[i]$ 被删了，实际实体落在了 $i-1$ 上）。
   • 路线 B（历史已经被删过）： 前面的某一步已经用过删除特权了（继承 dp1[i-1]），那当前数字 $a[i]$ 必须老老实实加上。即 dp1[i-1] + a[i]。

【竞赛评价】 这就是正解！巧妙地用多开一维状态，抹平了复杂规则带来的历史不确定性。拿到 100%。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

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];
    }

    // dp0: 一次都没删过； dp1: 删过一次
    vector<long long> dp0(n + 1, 0);
    vector<long long> dp1(n + 1, 0);

    // 【边界初始化】
    dp0[1] = a[1];
    // 只有一个元素时，如果把它删了数组就空了（不合法），所以设为极小值
    dp1[1] = -INF; 

    long long global_max = a[1];

    for (int i = 2; i <= n; ++i) {
        // 未删除状态转移：要么接上前一个没删过的，要么自己从头开始
        dp0[i] = max(a[i], dp0[i - 1] + a[i]);

        // 【核心】已删除状态转移：
        // 1. 刚刚删了 a[i]，所以直接继承 dp0[i-1]
        // 2. 之前就已经删过了，当前必须加上 a[i]，即 dp1[i-1] + a[i]
        // (注意防御 dp1[i-1] 是 -INF 的情况，防止相加下溢出)
        long long inherited_del = (dp1[i - 1] == -INF) ? -INF : dp1[i - 1] + a[i];
        dp1[i] = max(dp0[i - 1], inherited_del);

        // 全局最大值在 dp0 和 dp1 中打擂台
        global_max = max({global_max, dp0[i], dp1[i]});
    }

    cout << global_max << "\n";
    return 0;
}

版本四：双状态 DP + 空间优化（时间 $O(n)$，空间 $O(1)$）—— 满分极致版

【空间复杂度分析与优化】 观察版本三的转移方程，无论是 dp0[i] 还是 dp1[i]，计算时都仅仅只依赖了 $i-1$ 这一个时刻的状态。 既然如此，我们完全可以用两个滚动变量 no_del 和 one_del 替换掉两个庞大的数组。

🚨 致命易错点（The Temporary Variable Trap）： 当计算新的 one_del 时，你需要用到旧的 no_del。如果你先把 no_del 给更新了，那么 one_del 就会读到已经被污染的未来数据！必须使用 temp 变量，或者先算出新的值再统一赋值。

【竞赛评价】 完美无瑕，代码短小精悍，内存占用降到最低。这是 NOI 金牌级选手信手拈来的肌肉记忆写法。

#include <iostream>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

int main() {
    // 竞赛必备的快速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    long long first_val;
    cin >> first_val;

    // 滚动变量初始化
    long long no_del = first_val;
    long long one_del = -INF; // 第一个元素不可删除，标记为极小值
    long long global_max = first_val;

    for (int i = 2; i <= n; ++i) {
        long long val;
        cin >> val;

        // 【易错点防御】必须先暂存上一轮的 no_del 和 one_del
        long long prev_no_del = no_del;
        long long prev_one_del = one_del;

        // 计算当前轮的 no_del (等价于基础的最大子数组和)
        no_del = max(val, prev_no_del + val);

        // 计算当前轮的 one_del (抉择：是此刻删，还是过去早删了)
        // 注意防止 -INF 加上一个负数导致下溢出
        long long inherited = (prev_one_del == -INF) ? -INF : prev_one_del + val;
        one_del = max(prev_no_del, inherited);

        // 打擂台取最优
        global_max = max({global_max, no_del, one_del});
    }

    cout << global_max << "\n";
    return 0;
}

🏆 教练的延伸点拨：

1. 状态机的拓展（State Machine）： 我们这道题是“最多删除 1 次”。如果变成“最多删除 $K$ 次”呢？其实就是定义 dp[i][j]，表示以 $i$ 结尾且删了 $j$ 次。转移方程自然就变成了 dp[i][j] = max(dp[i-1][j] + a[i], dp[i-1][j-1])。这叫做**“基于层级的状态转移”**，是高级 DP 的敲门砖！
2. 空集的非法性（Non-empty constraint）： 初始化 one_del = -INF 非常关键。如果一开始只有 1 个数，删了它子数组就为空了，这违反了“子数组”至少包含一个元素的定义。强行把非法状态置为负无穷，是屏蔽非法转移的常用手段。