你好！作为你的教练，我非常支持你自己动手为这道题目制作 OJ 测试数据。这不仅能让你站在“出题人”的角度重新审视题目，还能深刻体会如何通过数据梯度卡掉错误或低效的算法。

下面为你提供符合 NOIP C++14 竞赛标准的数据生成器完整代码。

该生成器不仅会生成 1.in ~ 10.in，还会同时运行最优的 Kadane 算法（$O(n)$ 时间，$O(1)$ 空间）直接秒出标准答案并写入 1.out ~ 10.out。

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

为了区分出 $O(n^3)$、$O(n^2)$ 和 $O(n)$ 的算法，同时考察各种易错边界，我设计了如下 10 个测试点：

(注：最大的 .in 文件约为 600KB，10 个测试点总计不到 2.5MB，打成 ZIP 压缩包只需几百 KB，完全符合你的要求)

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

请新建一个文件夹，将此代码保存为 data_maker.cpp 并编译运行。它会在同目录下瞬间生成 20 个文件（10个输入，10个输出）。

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

using namespace std;

// 枚举不同的数据生成模式
enum DataType {
    RANDOM_MIXED = 0, // 全随机 (正负混合)
    ALL_NEGATIVE,     // 全负数
    ALL_POSITIVE,     // 全正数
    ALTERNATING,      // 正负交替
    ONE_POSITIVE,     // 只有一个正数，其余全为负数
    SMALL_VALUES      // 绝对值极小的数据
};

// 使用 mt19937 作为高质量随机数生成器 (比 rand() 更好，且在 C++11/14 中是标准)
mt19937 rng(1337); // 固定种子保证每次生成的数据一致，方便复现

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

// 核心求解函数 (Kadane算法 O(N) 空间 O(1))，用于生成标准答案 .out
long long solve_correct_answer(const vector<int>& a) {
    if (a.empty()) return 0;
    long long local_max = a[0];
    long long global_max = a[0];
    for (size_t i = 1; i < a.size(); ++i) {
        // 防止相加溢出用 long long（虽然本题 10^5 * 10^4 = 10^9 不会溢出 int，但好习惯要保持）
        local_max = max((long long)a[i], local_max + a[i]);
        global_max = max(global_max, local_max);
    }
    return global_max;
}

// 生成单个测试点数据的函数
void generate_test_case(int test_id, 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_NEGATIVE:
            for (int i = 0; i < n; ++i) a[i] = get_rand(-10000, -1);
            break;
        case ALL_POSITIVE:
            for (int i = 0; i < n; ++i) a[i] = get_rand(1, 10000);
            break;
        case ALTERNATING:
            for (int i = 0; i < n; ++i) {
                if (i % 2 == 0) a[i] = get_rand(1, 10000);
                else a[i] = get_rand(-10000, -1);
            }
            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, 10000); // 随机安插一个正数
            break;
        case SMALL_VALUES:
            for (int i = 0; i < n; ++i) a[i] = get_rand(-5, 5);
            break;
    }

    // --- 写入 .in 文件 ---
    string in_filename = to_string(test_id) + ".in";
    ofstream fin(in_filename);
    if (!fin) {
        cerr << "无法创建文件: " << in_filename << "\n";
        return;
    }
    // 写入 n
    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 << " generated successfully. (N = " << n << ")\n";
}

int main() {
    // 优化 I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << "开始生成测试数据...\n";

    // 1-3 测试点：规模极小，用于基础验证与全正/全负边界
    generate_test_case(1, 10, RANDOM_MIXED);
    generate_test_case(2, 20, ALL_NEGATIVE);
    generate_test_case(3, 50, ALL_POSITIVE);

    // 4 测试点：规模500，卡掉 O(n^3) 暴力枚举
    generate_test_case(4, 500, RANDOM_MIXED);

    // 5-6 测试点：规模达到上万，卡掉 O(n^2) 的前缀和枚举方案
    generate_test_case(5, 5000, RANDOM_MIXED);
    generate_test_case(6, 10000, RANDOM_MIXED);

    // 7-10 测试点：极限规模 10^5，各种刁钻场景考验 O(n) 算法的鲁棒性
    generate_test_case(7, 100000, ALTERNATING);  // 频繁的正负切换
    generate_test_case(8, 100000, ONE_POSITIVE); // 仅有一个正数
    generate_test_case(9, 100000, SMALL_VALUES); // 绝对值极小，频繁越过0
    generate_test_case(10, 100000, RANDOM_MIXED);// 纯极限大随机数据

    cout << "全部测试数据生成完毕！文件较多，请在当前目录下查看。\n";

    return 0;
}

教练的工程提示：

1. 种子（Seed）的固定：我在代码里使用了 mt19937 rng(1337);。在工程和出题规范中，生成器的随机数种子必须是固定的常量。这样做的目的是保证你换一台电脑、过了一年再重新编译运行这个生成器，生成的数据依然是完全一模一样的。这对于重现 Bug 或分享测试数据非常有帮助。
2. 纯迭代避免爆栈：solve_correct_answer 中全程使用了无递归的纯迭代（for循环扫描），即便把 $N$ 加大到 $10^8$ 也只会消耗 $O(1)$ 的调用栈空间，绝不会 Stack Overflow。
3. 输出流的优化：如果数据达到 $N=10^6$，频繁使用 std::endl 会导致严重的 I/O 耗时，因此在写文件时全部使用了 \n。

你现在可以编译并运行这份代码，它会在同目录下为你制作好完美的 OJ 测试数据包了！遇到不懂的地方随时问我。

你好！作为你的教练，我非常赞赏你这种**“从暴力到最优”**的阶梯式学习方法。在NOI/CSP等竞赛中，哪怕正解一时想不出，能稳稳打出暴力部分分解（Partial Score）也是极具战略意义的。

针对题目一：最大子数组和（Maximum Subarray Sum），我将为你展示4个版本的完整C++14代码。我们将一起经历从 $O(n^3)$ 到 $O(n^2)$，再到 $O(n)$，最后优化空间到 $O(1)$ 的思考全过程。

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

【思考过程】 最直观的想法是：枚举子数组的左端点 L 和右端点 R，然后再用一个循环从 L 加到 R 计算和，最后比较出最大值。 【竞赛评价】 对于 $n=10^5$ 的数据，计算量大概在 $10^{15}$ 级别，必定 TLE（超时）。通常只能拿 20%~30% 的部分分（对应 $n \le 100$ 的数据）。

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

using namespace std;

const long long INF = 1e18; // 使用极小值初始化，防止全是负数的情况

int main() {
    // 开启快速IO，NOIP竞赛标配
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // 使用 1-based 索引，符合竞赛习惯
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    long long global_max = -INF; // 【易错点1】千万不要初始化为0！如果全负数答案就是错的

    // 枚举左端点 L
    for (int L = 1; L <= n; ++L) {
        // 枚举右端点 R
        for (int R = L; R <= n; ++R) {
            long long current_sum = 0;
            // 计算区间 [L, R] 的和
            for (int k = L; k <= R; ++k) {
                current_sum += a[k];
            }
            // 更新全局最大值
            global_max = max(global_max, current_sum);
        }
    }

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

版本二：前缀和/递推优化暴力（时间 $O(n^2)$，空间 $O(n)$）

【时间复杂度优化建议】 观察版本一，当右端点从 R-1 移到 R 时，前面的和其实已经算过了！即 Sum[L...R] = Sum[L...R-1] + a[R]。我们完全可以去掉最内层的第三重循环。 【竞赛评价】 虽然降了一维，但对于 $n=10^5$ 依然有 $10^{10}$ 的计算量，还是会 TLE，大概能拿到 50%~60% 的分数（对应 $n \le 5000$）。

#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) {
        long long current_sum = 0; // 记录从 L 开始的累加和
        // 枚举右端点 R
        for (int R = L; R <= n; ++R) {
            current_sum += a[R]; // 【关键优化】复用前一步的结果，O(1) 算出新和
            global_max = max(global_max, current_sum);
        }
    }

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

版本三：一维动态规划（时间 $O(n)$，空间 $O(n)$）—— 黄金法则介入

【时间复杂度优化建议】 $O(n^2)$ 的痛点在于我们枚举了“所有的起始点”。如果换个思路，强行规定**“以当前元素 $i$ 作为结尾”**（DP黄金法则），那么我们其实只关心“前面的那一坨加起来是不是正数”。如果是正数，就接上；如果是负数，果断抛弃，从自己重新开始！ 【竞赛评价】 恭喜你！时间复杂度降到 $O(n)$，可以轻松通过 $n=10^5$ 甚至 $10^7$ 的数据，拿到 100% (AC)。

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

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] 表示：以第 i 个元素结尾的最大连续子数组和
    vector<long long> dp(n + 1, 0);
    
    // 【边界条件】以第1个元素结尾的最大和就是它自己
    dp[1] = a[1];
    long long global_max = dp[1]; // 记录全局答案

    for (int i = 2; i <= n; ++i) {
        // 【核心转移方程】
        // 抉择1：跟前面的接在一起 -> dp[i-1] + a[i]
        // 抉择2：抛弃前面，自己单干 -> a[i]
        dp[i] = max(a[i], dp[i - 1] + a[i]);
        
        // 全局最优解不一定在最后，必须随时打擂台
        global_max = max(global_max, dp[i]);
    }

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

版本四：动态规划 + 空间压缩（时间 $O(n)$，空间 $O(1)$）—— 终极解法

【空间复杂度分析与优化】 仔细观察版本三的代码：dp[i] = max(a[i], dp[i - 1] + a[i])。 计算当期的 dp[i] 时，我们只需要用到 dp[i-1] 的值。至于 dp[i-2]、dp[i-3] 早就没有利用价值了。既然如此，为什么要开辟一个长达 $n$ 的数组呢？ 【竞赛评价】 这是考场上最完美的答案，通常被称为 Kadane算法。不仅速度极快，还能省下大笔内存空间。体现了极高的算法素养。

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    // 快速IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    long long a_1;
    cin >> a_1; // 单独读取第一个数进行初始化

    // 【关键优化】只使用两个变量代替原先的 dp 数组
    long long local_max = a_1;  // 代表 dp[i-1]，即上一轮的局部最优
    long long global_max = a_1; // 代表全体最优解

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

        // 【状态转移】直接滚动覆盖 local_max 变量
        local_max = max(current_val, local_max + current_val);
        
        // 更新全局答案
        global_max = max(global_max, local_max);
    }

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

🏆 教练的重点叮嘱：

1. 数据范围保护（防爆 int）：虽然本题的数据范围 $10^5 \times 10^4 = 10^9$ 刚好在 32位 signed int 范围内，但我故意全篇使用了 long long。在实际NOI竞赛中，求**“前缀和”、“累加和”一律用 long long 兜底**是非常良好的习惯，防止因为极端数据导致溢出丢分。
2. 负数全家桶陷阱：遇到求最大值的问题，初始化 ans = 0 是新手最常犯的错误！如果输入序列是 -5 -2 -9，正确输出是 -2，但若初始化为 0 会错误输出 0。必须用 ans = a[1] 或 ans = -1e18 来初始化。
3. 空间滚动的艺术：版本四中不仅优化了 dp 数组，甚至连原数组 a 都没有存进去（一边 cin 读入一边直接处理了）。这叫 “在线处理（Online Processing）”，在内存极度受限的极端题目中（如只给 4MB 空间），这是救命的技巧！