构建测试数据是深刻理解算法边界和极限的绝佳途径。

作为教练，我为你设计的这份数据生成器不仅包含了能够区分 $O(N^2)$ 和 $O(N)$ 复杂度的极大尺寸数据，还刻意构造了“单调递减”、“完全相同”、“V型震荡”等极其容易“卡死”漏洞代码的边界情况。

以下是完整的 C++ 数据生成器代码。你可以直接编译运行它，它会在当前目录下瞬间生成 1.in ~ 10.in 以及对应的标准答案 1.out ~ 10.out 文件。

测试点设计说明 (10个测试点)

为保证在不超过 2MB 限制的前提下卡掉 $O(N^2)$，最大的 $N$ 设为 $10^5$。每个文件包含 $10^5$ 个以空格分隔的最大 $10^9$ 的数字，文件大小约为 1.1 MB，完美符合要求。

1. Test 1: $N=1$。边界情况。无法完成买卖，答案必须为0。
2. Test 2: $N=2$。最小有效情况。正常的买入卖出。
3. Test 3: $N=10$。小数据随机。用于验证基础逻辑。
4. Test 4: $N=1000$。严格单调递减。无论怎么买都亏本，测试输出 $0$ 的逻辑，防止输出负数利润。
5. Test 5: $N=50000$。所有元素完全相同。没有任何波动，利润为 0，测试边界等于判断。
6. Test 6: $N=80000$。严格单调递增。必须在第一天买，最后一天卖。
7. Test 7: $N=10^5$。大数据，小波幅随机。普通的大规模测试，用于卡掉 $O(N^2)$ 暴力。
8. Test 8: $N=10^5$。大数据，全范围随机。数值高达 $10^9$。
9. Test 9: $N=10^5$。极限极差构造。强制第一天为 $1$，最后一天为 $10^9$，中间随机，验证最大答案承载能力。
10. Test 10: $N=10^5$。高频震荡构造 (W型/锯齿型)。频繁出现局部高点和低点，专门卡错误贪心（比如遇到下降就清空状态的代码）。

C++ 数据生成器代码

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

using namespace std;

// 【标准答案程序】使用最优的 O(N) 贪心DP计算答案，用于生成 .out 文件
long long solve_optimal(const vector<int>& p) {
    if (p.size() < 2) return 0;
    long long ans = 0;
    int min_price = p[0];
    for (size_t i = 1; i < p.size(); ++i) {
        ans = max(ans, (long long)p[i] - min_price);
        min_price = min(min_price, p[i]);
    }
    return ans;
}

// 随机数引擎初始化 (使用 mt19937 提供高质量随机数)
mt19937 rng(1337); // 固定种子保证每次生成的数据一致，方便OJ对账。如需不同可改为 random_device{}()

// 辅助函数：生成指定范围内的随机整数
int rand_int(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rng);
}

// 生成单个测试点的核心逻辑
void generate_test_case(int test_id) {
    int n = 0;
    vector<int> p;

    // 根据测试点编号，分配不同的生成策略
    switch (test_id) {
        case 1: // 边界情况：N=1
            n = 1;
            p.push_back(rand_int(1, 100));
            break;
        case 2: // 最小有效：N=2
            n = 2;
            p = {15, 30}; // 利润 15
            break;
        case 3: // 小数据随机：N=10
            n = 10;
            for(int i = 0; i < n; i++) p.push_back(rand_int(1, 100));
            break;
        case 4: // 单调递减 (0利润)
            n = 1000;
            for(int i = 0; i < n; i++) p.push_back(10000 - i);
            break;
        case 5: // 所有元素相同 (0利润)
            n = 50000;
            for(int i = 0; i < n; i++) p.push_back(88888);
            break;
        case 6: // 单调递增
            n = 80000;
            for(int i = 0; i < n; i++) p.push_back(i * 10 + 1);
            break;
        case 7: // 大数据，普通随机
            n = 100000;
            for(int i = 0; i < n; i++) p.push_back(rand_int(1, 10000));
            break;
        case 8: // 大数据，大范围随机
            n = 100000;
            for(int i = 0; i < n; i++) p.push_back(rand_int(1, 1000000000));
            break;
        case 9: // 极限差值 (开局极小，结尾极大)
            n = 100000;
            p.push_back(1);
            for(int i = 1; i < n - 1; i++) p.push_back(rand_int(100, 10000000));
            p.push_back(1000000000);
            break;
        case 10: // 锯齿型高频震荡
            n = 100000;
            for(int i = 0; i < n; i++) {
                if (i % 2 == 0) p.push_back(rand_int(1, 1000));       // 偶数天低点
                else p.push_back(rand_int(900000000, 1000000000)); // 奇数天高点
            }
            break;
    }

    // 1. 生成并写入输入文件 .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 << p[i] << (i == n - 1 ? "" : " ");
    }
    fin << "\n";
    fin.close();

    // 2. 计算标准答案并写入输出文件 .out
    long long ans = solve_optimal(p);
    string out_filename = to_string(test_id) + ".out";
    ofstream fout(out_filename);
    fout << ans << "\n";
    fout.close();

    cout << "成功生成测试点 " << test_id << " (N = " << n << ", Answer = " << ans << ")" << "\n";
}

int main() {
    // 关闭同步，加速潜在的大规模控制台输出（虽然这里不多）
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << "开始生成测试数据...\n";
    for (int t = 1; t <= 10; ++t) {
        generate_test_case(t);
    }
    cout << "所有测试数据生成完毕，您可以将其打包上传至 OJ 系统。\n";

    return 0;
}

运行建议与时间复杂度评价

1. 编译与运行： 保存为 data_maker.cpp，执行 g++ data_maker.cpp -o data_maker -O2 -std=c++14，然后 ./data_maker。生成会在一瞬间（< 100毫秒）完成。
2. 生成复杂度优化：
   • 我们在写生成器时直接使用了 vector::push_back 和标准 $O(N)$ 循环，完全抛弃了递归调用，绝对不会爆栈。
   • 随机数采用了 <random> 库的 mt19937 引擎，这是算法竞赛生成大规模可靠随机数的标配，效率极高。
   • 不涉及除以 0 等异常计算，健壮性高。
3. 空间利用： 生成过程中 vector<int> p 的最大内存开销为 $10^5 \times 4 \text{ bytes} \approx 400 \text{ KB}$，远远低于一般电脑的运行内存，没有任何内存溢出风险。单个 10.in 最大尺寸约 $1.1 \text{ MB}$。

你好！很高兴看到你准备动手写代码了。在NOI（信息学奥赛）中，“先写出暴力保底，再逐步优化求满分” 是非常重要且稳妥的实战策略。

下面我将按照这个思路，为你提供三个版本的标准 C++14 题解代码。每个版本都是包含 main 函数的完整可运行代码，并配有详细的注释和复杂度分析。

版本一：基础暴力版 (Brute Force)

思路： 最直观的想法。我们用两层循环，外层循环枚举买入时间 i，内层循环枚举卖出时间 j（要求 j > i）。计算所有可能的利润 P[j] - P[i]，取其中的最大值。

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

using namespace std;

int main() {
    // 优化标准输入输出速度 (NOI必备技巧)
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

    // ans 初始化为0，如果所有交易都亏本，最大利润就是0 (不买不卖)
    int ans = 0; 

    // 外层循环：枚举买入的第 i 天
    for (int i = 0; i < n; ++i) {
        // 内层循环：枚举在第 i 天之后卖出的第 j 天
        // 【易错点】j 必须从 i + 1 开始，因为必须先买后卖
        for (int j = i + 1; j < n; ++j) { 
            // 如果卖出价比买入价高，尝试更新最大利润
            if (p[j] > p[i]) {
                ans = max(ans, p[j] - p[i]);
            }
        }
    }

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

• 时间复杂度分析： 外层循环执行 $N$ 次，内层循环平均执行 $N/2$ 次。总执行次数约为 $N^2/2$。时间复杂度为 $O(N^2)$。当 $N = 10^5$ 时，计算量达到 $5 \times 10^9$ 级别，一般评测机1秒内只能处理 $10^8$ 左右的运算，因此必定会 TLE (超时)。
• 空间复杂度分析： 仅使用了一个长度为 $N$ 的数组存储输入，空间复杂度为 $O(N)$。

版本二：预处理 Min-Max 模式版 (空间换时间)

思路： 运用你在图片中看到的模式。我们预先算出每一天及其左边的“历史最低价”（dpLeft），以及每一天及其右边的“未来最高价”（dpRight）。然后遍历一次每一天，假设在这天作为分界点，最大利润就是当天的 dpRight[i] - dpLeft[i]。

#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<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }

    // 针对特殊情况的处理：如果只有不到2天，无法完成买卖
    if (n < 2) {
        cout << 0 << "\n";
        return 0;
    }

    // dpLeft[i] 表示 [0...i] 范围内的最低价格
    vector<int> dpLeft(n);
    dpLeft[0] = p[0];
    for (int i = 1; i < n; ++i) {
        dpLeft[i] = min(dpLeft[i - 1], p[i]);
    }

    // dpRight[i] 表示 [i...n-1] 范围内的最高价格
    vector<int> dpRight(n);
    dpRight[n - 1] = p[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        dpRight[i] = max(dpRight[i + 1], p[i]);
    }

    int ans = 0;
    // 遍历所有的切分点 i，计算最大差值
    for (int i = 0; i < n; ++i) {
        // 【关键点】利润 = 未来能卖出的最高价 - 历史能买入的最低价
        ans = max(ans, dpRight[i] - dpLeft[i]); 
    }

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

• 时间复杂度分析： 我们对数组进行了三次并列的遍历（一次求 dpLeft，一次求 dpRight，一次算 ans）。总执行次数约为 $3N$。忽略常数，时间复杂度优化为 $O(N)$。可以轻松通过 $N = 10^5$ 的数据限制，拿到满分。
• 空间复杂度分析： 额外开辟了 dpLeft 和 dpRight 两个长度为 $N$ 的数组，空间复杂度为 $O(N)$。

版本三：最优状态压缩版 (Single Pass / 贪心 DP)

思路： 结合之前的引导，进一步思考：我们真的需要保存所有的后缀最大值或前缀最小值吗？ 当我们从左到右遍历股票价格时，站在第 $i$ 天思考：“如果我今天必须卖出，我的最大利润是多少？” 显然是“今天的价格”减去“今天之前的最低买入价”。 所以，我们只需在遍历过程中实时维护一个 min_price 变量即可，边遍历边更新答案。

#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<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }

    if (n < 2) {
        cout << 0 << "\n";
        return 0;
    }

    int ans = 0; 
    // 【关键点】初始化历史最低价为第一天的价格
    // 不要初始化为 0，否则如果股票价格全是正数，利润计算会出错
    int min_price = p[0]; 

    // 只进行一次遍历
    for (int i = 1; i < n; ++i) {
        // 1. 假设今天卖出，更新最大利润 ans
        // (如果今天价格比 min_price 还低，这里算出来是负数，ans由于初始为0，不会被更新)
        ans = max(ans, p[i] - min_price);
        
        // 2. 检查今天的价格能不能成为未来的“历史最低买入价”
        // 【易错点】更新 min_price 的操作放在后面或者前面都可以（因为当天买当天卖利润为0，不影响最大值ans）
        min_price = min(min_price, p[i]); 
    }

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

• 时间复杂度分析： 只有一个长度为 $N$ 的循环遍历，时间复杂度为 $O(N)$。常数更小，运行速度极快。
• 空间复杂度分析： 除了存储输入的数组 p 以外，只使用了常数个变量 ans 和 min_price。辅助空间复杂度被极致压缩到了 $O(1)$。(注：如果要求连输入数组都不存，直接在线读入在线处理，总体空间复杂度都可以降为 $O(1)$。)

教练总结

从 O(N^2) 到 O(N) 空间为 O(N)，再到 O(N) 空间为 O(1)。这体现了 NOI 竞赛中非常核心的优化思维链条：

1. 观察冗余计算： 暴力法中，对于每一个固定的买入日 i，都要向后扫描找最大值；换个 i，又要重新扫描一遍。
2. 空间换时间： 发现查询“极值”的过程有很多重叠，于是用数组 dp 预先记录下来，以后查表只需要 $O(1)$。
3. 状态压缩降维： 发现状态转移只与“上一个状态”有关（今天之前的最低价，只由昨天之前的最低价和昨天价格决定），于是把 $O(N)$ 的 dp 数组压缩成了一个 $O(1)$ 的变量。

以后在遇到复杂的 DP 题目时，也请按照：写出状态转移 -> 画出数组 -> 观察依赖关系 -> 压缩维度的步骤来！