你好！我是你的 OI 教练。我们终于来到了“子数组 DP 系列”数据生成的收官战。

针对题目五：最长湍流子数组（Longest Turbulent Subarray），数据生成的关键在于构造**“状态切换的连续性”与“突发性中断”**。如果只是纯随机数，由于数值范围大，相邻元素相等的概率极低，且符号翻转的概率几乎恒定为 1/2，很难测出那些在处理“相等元素（Equal elements）”或“连续上升/下降（Monotonic）”时逻辑有误的代码。

为此，我设计了多种模式，包括完美的正弦波、阶梯波以及高频碰撞。

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

(注：单文件最大约 $600\text{KB}$，全套数据 ZIP 包约 $1.5\text{MB}$，完全符合 2MB 限制。)

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

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

using namespace std;

// 数据生成模式
enum DataType {
    RANDOM_MIXED = 1,
    ALL_EQUAL,      // 全相等
    PERFECT_ZIGZAG, // 完美的 1, 2, 1, 2...
    MONOTONIC,      // 单调递增
    STAIRCASE,      // 1, 1, 2, 2...
    NARROW_RANGE,   // 极窄值域 (0, 1, 2)
    LONG_ZIGZAG_BREAK // 长湍流接中断
};

// 固定种子确保可复现
mt19937 rng(512);

int get_rand(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rng);
}

// 核心求解函数 (标准答案 O(N) 空间 O(1))
int solve_correct_answer(int n, const vector<int>& a) {
    if (n <= 1) return n;
    int up = 1, down = 1, global_max = 1;
    for (int i = 1; i < n; ++i) {
        if (a[i] > a[i - 1]) {
            up = down + 1;
            down = 1;
        } else if (a[i] < a[i - 1]) {
            down = up + 1;
            up = 1;
        } else {
            up = 1;
            down = 1;
        }
        global_max = max({global_max, up, down});
    }
    return global_max;
}

// 模式化生成数组
vector<int> generate_array(int n, DataType type) {
    vector<int> a(n);
    switch (type) {
        case ALL_EQUAL:
            fill(a.begin(), a.end(), get_rand(1, 100));
            break;
        case PERFECT_ZIGZAG:
            for (int i = 0; i < n; ++i) a[i] = (i % 2 == 0 ? 1 : 2);
            break;
        case MONOTONIC:
            for (int i = 0; i < n; ++i) a[i] = i;
            break;
        case STAIRCASE:
            for (int i = 0; i < n; ++i) a[i] = i / 2;
            break;
        case NARROW_RANGE:
            for (int i = 0; i < n; ++i) a[i] = get_rand(0, 2);
            break;
        case LONG_ZIGZAG_BREAK:
            for (int i = 0; i < n; ++i) a[i] = (i % 2 == 0 ? 1 : 2);
            if (n > 5) a[n / 2] = a[n / 2 - 1]; // 在中间打断
            break;
        default:
            for (int i = 0; i < n; ++i) a[i] = get_rand(-1000000000, 1000000000);
            break;
    }
    return a;
}

void generate_test_case(int test_id, int n, DataType type) {
    vector<int> a = generate_array(n, type);

    // 写 .in 文件
    string in_name = to_string(test_id) + ".in";
    ofstream fin(in_name);
    fin << n << "\n";
    for (int i = 0; i < n; ++i) {
        fin << a[i] << (i == n - 1 ? "" : " ");
    }
    fin << "\n";
    fin.close();

    // 写 .out 文件
    int ans = solve_correct_answer(n, a);
    string out_name = to_string(test_id) + ".out";
    ofstream fout(out_name);
    fout << ans << "\n";
    fout.close();

    cout << "Test Case " << test_id << " OK. (N=" << n << ", Type=" << type << ", Ans=" << ans << ")\n";
}

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

    cout << "正在生成湍流子数组测试数据...\n";

    generate_test_case(1, 10, RANDOM_MIXED);
    generate_test_case(2, 100, ALL_EQUAL);
    generate_test_case(3, 200, PERFECT_ZIGZAG);
    generate_test_case(4, 500, MONOTONIC);
    generate_test_case(5, 2000, RANDOM_MIXED);
    generate_test_case(6, 5000, STAIRCASE);
    generate_test_case(7, 10000, RANDOM_MIXED);
    generate_test_case(8, 100000, NARROW_RANGE);
    generate_test_case(9, 100000, LONG_ZIGZAG_BREAK);
    generate_test_case(10, 100000, RANDOM_MIXED);

    cout << "生成完毕。\n";
    return 0;
}

👨‍🏫 教练的最后叮嘱：

1. 关于 $N=1$ 的处理：在测试点 1 这种随机数据中，可能会随出极小的 $N$。标准答案代码必须能正确处理 $N=1$ 输出 1，否则 OJ 的第一个测试点就会报错。
2. 数值范围防护：在第 10 个测试点，我将数值范围设为了 $\pm 10^9$。如果选手的代码里使用了 a[i] - a[i-1] 且没用 long long，或者在某些中间计算环节涉及了乘法，极易爆掉 int。虽然最优解不需要减法（直接比较即可），但这种数据设计能很好地筛选出那些“写代码不细心”的学生。
3. 无 Exception 保证：由于这道题不需要除法，且我们使用了纯迭代逻辑，因此不会出现除以零或爆栈的异常。

恭喜你完成了“子数组优化 DP”系列的所有测试数据建设！这是一套非常高质量的专项练习题，能够极大提升学生对 DP 状态定义的理解。如果有任何其他题目需求，欢迎随时向我咨询。

你好！我是你的教练。我们来到了这组“子数组优化”系列题目的最后一关——题目五：最长湍流子数组（Longest Turbulent Subarray）。

这道题是动态规划中“状态机思维”的经典应用。湍流（Turbulence）要求符号在 < 和 > 之间交替，这意味着当前的状态（是变大了还是变小了）直接决定了下一个合法的动作。

下面我们按照从暴力枚举到 $O(1)$ 空间 DP 的过程进行演进。

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

【思考过程】 最稳妥的保底思路：枚举所有可能的子数组区间 $[L, R]$。对每一个区间，写一个独立的函数来检查它是否满足“湍流”定义（即每相邻两个比较符都相反）。

【竞赛评价】 时间复杂度 $O(n^3)$。在 $N=10^5$ 时完全不可行，仅能通过 $N \le 100$ 的极小测试点。

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

using namespace std;

// 检查区间 [L, R] 是否是湍流子数组
bool is_turbulent(const vector<int>& a, int L, int R) {
    if (L == R) return true; // 长度为 1 总是湍流
    for (int k = L + 1; k < R; ++k) {
        // 湍流要求：a[k-1] < a[k] > a[k+1] 或者 a[k-1] > a[k] < a[k+1]
        // 逻辑等价于：(a[k] - a[k-1]) 与 (a[k+1] - a[k]) 乘积为负（符号相反）
        long long diff1 = a[k] - a[k-1];
        long long diff2 = a[k+1] - a[k];
        if (!((diff1 > 0 && diff2 < 0) || (diff1 < 0 && diff2 > 0))) {
            return false;
        }
    }
    // 检查长度为 2 的情况：只要不相等就是湍流
    if (R - L == 1) return a[L] != a[L+1];
    return true;
}

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

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

    int max_len = 1;
    for (int L = 0; L < n; ++L) {
        for (int R = L; R < n; ++R) {
            if (is_turbulent(a, L, R)) {
                max_len = max(max_len, R - L + 1);
            }
        }
    }
    cout << max_len << endl;
    return 0;
}

版本二：线性探测优化（时间 $O(n^2)$，空间 $O(n)$）

【优化建议】 当我们固定左端点 $L$ 时，如果探测到 $R$ 时湍流断了，那么 $R+1, R+2 \dots$ 肯定也不是以 $L$ 开头的湍流了。因此不需要每次都重新检查。

【竞赛评价】 复杂度 $O(n^2)$。能通过 $N \le 5000$ 的数据，预期得分 50~60 分。

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

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

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

    int max_len = 1;
    for (int L = 0; L < n; ++L) {
        // 固定 L，尝试向右尽可能远地探测 R
        for (int R = L + 1; R < n; ++R) {
            if (R == L + 1) {
                if (a[R] == a[R-1]) break; // 相等直接断开
            } else {
                // 检查新的元素是否与前一对维持相反的符号
                long long d1 = a[R-1] - a[R-2];
                long long d2 = a[R] - a[R-1];
                if (!((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0))) break;
            }
            max_len = max(max_len, R - L + 1);
        }
    }
    cout << max_len << endl;
    return 0;
}

版本三：一维状态机 DP（时间 $O(n)$，空间 $O(n)$）

【思考过程】 核心在于：“以 $i$ 结尾的最大长度”取决于“以 $i-1$ 结尾时的比较符号”。 我们需要两个状态：

1. up[i]：以 $i$ 结尾，且满足 $a[i-1] < a[i]$（当前是上升趋势）的最长湍流长度。
2. down[i]：以 $i$ 结尾，且满足 $a[i-1] > a[i]$（当前是下降趋势）的最长湍流长度。

【状态转移】

• 如果 $a[i] > a[i-1]$：我可以接在之前的“下降趋势”后面。up[i] = down[i-1] + 1，同时 down[i] 复位为 1。
• 如果 $a[i] < a[i-1]$：我可以接在之前的“上升趋势”后面。down[i] = up[i-1] + 1，同时 up[i] 复位为 1。
• 如果 $a[i] == a[i-1]$：湍流彻底中断。up[i] = 1, down[i] = 1。

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

    if (n == 0) { cout << 0 << endl; return 0; }

    // up[i] 表示以 i 结尾且 a[i-1] < a[i] 的最长湍流长度
    vector<int> up(n, 1);
    // down[i] 表示以 i 结尾且 a[i-1] > a[i] 的最长湍流长度
    vector<int> down(n, 1);

    int global_max = 1;

    for (int i = 1; i < n; ++i) {
        if (a[i] > a[i-1]) {
            up[i] = down[i-1] + 1; // 升序，必须接在之前的降序后面
            down[i] = 1;           // 此时不可能以降序结尾
        } else if (a[i] < a[i-1]) {
            down[i] = up[i-1] + 1; // 降序，必须接在之前的升序后面
            up[i] = 1;
        } else {
            // 相等则全部重置
            up[i] = 1;
            down[i] = 1;
        }
        global_max = max({global_max, up[i], down[i]});
    }

    cout << global_max << endl;
    return 0;
}

版本四：DP 空间压缩（时间 $O(n)$，空间 $O(1)$）—— 终极解法

【空间优化思考】 计算 up[i] 只用了 down[i-1]，计算 down[i] 只用了 up[i-1]。我们完全不需要数组，只需要两个变量不断交替更新。

【竞赛评价】 $O(n)$ 时间，$O(1)$ 空间。这是处理此类“序列状态切换”问题的最高标准写法。

#include <iostream>
#include <algorithm>

using namespace std;

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

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

    // 处理 n=1 的特例
    if (n == 1) {
        int temp; cin >> temp;
        cout << 1 << endl;
        return 0;
    }

    int prev_val;
    cin >> prev_val;

    // 使用滚动变量优化
    int up = 1;   // 记录以上升结束的当前最长长度
    int down = 1; // 记录以下降结束的当前最长长度
    int global_max = 1;

    for (int i = 1; i < n; ++i) {
        int curr_val;
        cin >> curr_val;

        if (curr_val > prev_val) {
            // 当前是上升，它能接在之前的下降后面
            up = down + 1;
            down = 1; // 重置另一状态
        } else if (curr_val < prev_val) {
            // 当前是下降，它能接在之前的上升后面
            down = up + 1;
            up = 1;   // 重置另一状态
        } else {
            // 相等情况，湍流全部断裂，重置为 1
            up = 1;
            down = 1;
        }
        
        global_max = max({global_max, up, down});
        prev_val = curr_val; // 更新“历史”供下一轮使用
    }

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

🏆 教练的重点总结：

1. 时间的平摊分析：这道题其实也可以用“双指针/滑动窗口”来做，时间复杂度也是 $O(n)$。但用 DP 的状态机写法更具通用性，特别是当你遇到更复杂的交替规则时（比如长度为 3 的循环规则）。
2. 数据范围细节：在计算 a[i] - a[i-1] 时，如果题目数据很大，相减可能会溢出 int。在版本四中，我直接通过 if (curr_val > prev_val) 进行逻辑比较，从而完全规避了减法溢出的问题，这是更稳妥的工程习惯。
3. 理解“重置为 1”：很多同学会忘记在不满足条件时把 up 或 down 重置为 1。记住，湍流长度至少包含当前这一个元素，所以重置值是 1 而不是 0。

这道题完成后，你已经掌握了连续子数组 DP 的全套功法！从基础求和到乘积翻转，再到环形处理和状态扩展。恭喜你！