太棒了！构造这道“最长山脉”的测试数据，比上一题“买卖股票”要考验功底得多。因为这道题有一个隐藏的坑：题目限定了数组元素 $A_i \le 10^4$。

如果我们要卡死 $O(N^2)$ 的暴力算法，最有效的方法是造一个非常长、非常长的单调斜坡。但是，由于元素最大只能到 $10000$，我们无法造出一个长度为 $10^5$ 的严格单调递增斜坡！因此，我们需要利用限制，在一个 $10^5$ 的数组里，连续放置多个高度为 $10000$ 的大山脉，以此来最大化 $O(N^2)$ 算法的扩展步数。

此外，“平顶山”（有相邻相同元素）是极其容易让状态机写错的边界情况，我们必须重点覆盖。

以下是为你量身定制的完整 C++ 数据生成器：

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

由于 $N \le 10^5, A_i \le 10^4$，最大的 10.in 文件大小不超过 600 KB，完美低于你 2MB 的要求。

1. Test 1: $N=1$。极限边界。无法构成山脉。
2. Test 2: $N=2$。无法构成山脉的最小长度。
3. Test 3: $N=3$。标准小山脉。最基础的正常通过情况。
4. Test 4: $N=10^5$。只增不减 (阶梯状)。没有下坡，答案必须为0。用于测试状态是否会错误地在单调数组里触发。
5. Test 5: $N=10^5$。全平原 (所有元素相同)。极其容易让暴力代码死循环或 DP 忘记清零。
6. Test 6: $N=10^5$。连绵巨峰构造 (卡 $O(N^2)$ 专用)。由连续的最大高度山脉（长达20000）相连组成，使暴力枚举向左右扩展的步数达到极限。
7. Test 7: $N=10^5$。平顶山和平谷底 (打断机制测试)。形如 1 2 3 3 2 1。由于 3 和 3 之间是平坦的，不满足严格单调，所以这不能算作一座完整的山，两边必须各自断开。
8. Test 8: $N=10^5$。高频锯齿 (防错误剪枝)。形如 0 10000 0 10000。全是长度为3的微小山脉。
9. Test 9: $N=10^5$。包含平缓阶梯的伪山脉。上坡时走两步平一步，验证上升状态是否被正确阻断。
10. Test 10: $N=10^5$。全随机大数据。大乱斗测试综合稳定性。

C++ 数据生成器代码

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

using namespace std;

// 【标准答案程序】使用最优 O(N) 贪心DP计算答案，用于生成 .out 文件
int solve_optimal(const vector<int>& a) {
    int n = a.size();
    if (n < 3) return 0;
    
    vector<int> dpLeft(n, 0);
    for (int i = 1; i < n; ++i) {
        if (a[i] > a[i - 1]) dpLeft[i] = dpLeft[i - 1] + 1;
        else dpLeft[i] = 0;
    }

    vector<int> dpRight(n, 0);
    for (int i = n - 2; i >= 0; --i) {
        if (a[i] > a[i + 1]) dpRight[i] = dpRight[i + 1] + 1;
        else dpRight[i] = 0;
    }

    int ans = 0;
    for (int i = 1; i < n - 1; ++i) {
        if (dpLeft[i] > 0 && dpRight[i] > 0) {
            ans = max(ans, dpLeft[i] + dpRight[i] + 1);
        }
    }
    return ans;
}

// 初始化高质量随机数引擎 (固定种子1337保证每次运行生成的数据一模一样)
mt19937 rng(1337);

// 生成指定范围内的随机整数
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> a;

    switch (test_id) {
        case 1: // 边界情况 N=1
            n = 1; a.push_back(rand_int(0, 10000)); 
            break;
        case 2: // 边界情况 N=2
            n = 2; a.push_back(100); a.push_back(200); 
            break;
        case 3: // 基础山脉 N=3
            n = 3; a = {10, 100, 20}; 
            break;
        case 4: // 非递减 (无山脉)
            n = 100000;
            for(int i = 0; i < n; i++) a.push_back(min(i, 10000));
            break;
        case 5: // 完全平原 (无山脉)
            n = 100000;
            for(int i = 0; i < n; i++) a.push_back(5555);
            break;
        case 6: // 连绵巨峰 (卡O(N^2)极限扩展步数)
            n = 100000;
            {
                int v = 0, dir = 1;
                for(int i = 0; i < n; i++) {
                    a.push_back(v);
                    v += dir;
                    // 由于 A_i <= 10000，到达 10000 必须拐弯
                    if (v == 10000) dir = -1;
                    else if (v == 0) dir = 1;
                }
            }
            break;
        case 7: // 平顶山与平底谷 (严格单调性阻断测试)
            n = 100000;
            for(int i = 0; i < n; i++) {
                int mod = i % 1000;
                if (mod < 490) a.push_back(mod);              // 上坡
                else if (mod <= 510) a.push_back(489);        // 平顶
                else if (mod < 990) a.push_back(1000 - mod);  // 下坡
                else a.push_back(10);                         // 平谷底
            }
            break;
        case 8: // 极限锯齿
            n = 100000;
            for(int i = 0; i < n; i++) a.push_back(i % 2 == 0 ? 0 : 10000);
            break;
        case 9: // 阶梯式伪山坡 (0 0 1 1 2 2...)
            n = 100000;
            for(int i = 0; i < n; i++) {
                int cycle = i % 4000;
                if (cycle < 2000) a.push_back(cycle / 2);         // 上升并包含平坡
                else a.push_back((4000 - cycle) / 2);             // 下降并包含平坡
            }
            break;
        case 10: // 纯随机大数据
            n = 100000;
            for(int i = 0; i < n; i++) a.push_back(rand_int(0, 10000));
            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 << a[i] << (i == n - 1 ? "" : " ");
    }
    fin << "\n";
    fin.close();

    // 2. 算答案并生成 .out 文件
    int ans = solve_optimal(a);
    string out_filename = to_string(test_id) + ".out";
    ofstream fout(out_filename);
    fout << ans << "\n";
    fout.close();

    cout << "成功生成测试点 " << test_id << " (N = " << n << ", 预期答案 = " << 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. 极速生成无爆栈风险： 所有构造全由 $O(N)$ 的 for 循环和数学取模实现，无图/树遍历操作，没有递归，速度在几十毫秒级别内瞬间成形。
2. 安全可靠： 分母为常量（如 cycle / 2）或已严格规避 0，杜绝 Divide by Zero 异常崩溃。
3. 杀伤力极强： Test 6 和 Test 7 对逻辑不严密的代码有毁灭性打击。如果学生的代码没有正确处理 dpLeft[i] = 0 的情况（遇到平地依然继承长度），在 Test 7 必将暴露无遗。如果写了循环嵌套拓展，必定卡死在 Test 6 连绵巨峰中。

你可以直接使用 g++ mountain_maker.cpp -o maker -O2 -std=c++14 编译执行，立刻收获高质量的试题数据包！

把思路转化为代码是算法竞赛中最重要的一环。在 NOI 竞赛中，循序渐进地写代码不仅能帮我们在考场上稳拿部分分，还能通过暴力程序来对拍（验证）最终的优化程序。

下面我将为你提供三个版本的标准 C++14 题解代码，从基础的暴力延展，到标准的左右 DP 预处理，再到极致的 $O(1)$ 空间单次遍历。

版本一：基础暴力版 (中心扩展法)

思路： 这是最符合直觉的写法。一座山一定有一个“山峰”。我们枚举数组中每一个可能成为山峰的元素 $A_i$（$i$ 从 $1$ 到 $N-2$），然后尝试向左和向右尽可能延伸，直到不再严格递减为止。

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

    // 如果数组长度小于3，绝对不可能形成山脉
    if (n < 3) {
        cout << 0 << "\n";
        return 0;
    }

    int ans = 0;

    // 枚举每一个可能成为山峰的点（排除了首尾两个元素）
    for (int i = 1; i < n - 1; ++i) {
        int left = i;
        int right = i;

        // 向左寻找左山脚：只要左边比当前小，就一直往左走
        while (left > 0 && a[left - 1] < a[left]) {
            left--;
        }

        // 向右寻找右山脚：只要右边比当前小，就一直往右走
        while (right < n - 1 && a[right + 1] < a[right]) {
            right++;
        }

        // 【关键点】判断是否真正形成了山脉！
        // 必须既有上坡 (left < i) 又有下坡 (right > i)
        if (left < i && right > i) {
            // 更新最长山脉的长度
            ans = max(ans, right - left + 1);
        }
    }

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

• 时间复杂度分析： 外层循环枚举山峰执行 $N$ 次。最坏情况下（例如数组形如 1 2 3 ... N ... 3 2 1，一个巨大的山），向左向右扫描会遍历整个数组，内层循环执行 $O(N)$ 次。总时间复杂度为 $O(N^2)$。当 $N = 10^5$ 时，一定会 TLE (超时)。
• 空间复杂度分析： 仅使用了一个长度为 $N$ 的数组存储输入，空间复杂度为 $O(N)$。

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

思路： 运用图片红框里的 dpLeft 和 dpRight 概念。我们预先算出每个点作为“山峰”时，它左边的“连续爬坡长度”和右边的“连续下坡长度”。这样在枚举山峰时，查询长度的时间就从 $O(N)$ 降到了 $O(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 < 3) {
        cout << 0 << "\n";
        return 0;
    }

    // dpLeft[i] 表示以 a[i] 结尾的左侧连续严格递增长度 (不含自身)
    vector<int> dpLeft(n, 0);
    // 从左向右正向遍历
    for (int i = 1; i < n; ++i) {
        if (a[i] > a[i - 1]) {
            dpLeft[i] = dpLeft[i - 1] + 1;
        } else {
            // 【易错点】一旦平坦或下降，连续递增状态破裂，立刻归零
            dpLeft[i] = 0; 
        }
    }

    // dpRight[i] 表示以 a[i] 开头的右侧连续严格递减长度 (不含自身)
    vector<int> dpRight(n, 0);
    // 【关键点】必须从右向左反向遍历
    for (int i = n - 2; i >= 0; --i) {
        if (a[i] > a[i + 1]) {
            dpRight[i] = dpRight[i + 1] + 1;
        } else {
            dpRight[i] = 0;
        }
    }

    int ans = 0;
    // 遍历每一个点，看它能否作为山峰
    for (int i = 1; i < n - 1; ++i) {
        // 必须同时满足有上坡 (dpLeft[i] > 0) 和下坡 (dpRight[i] > 0)
        if (dpLeft[i] > 0 && dpRight[i] > 0) {
            // 山脉总长度 = 左坡长 + 右坡长 + 山峰自己(1)
            ans = max(ans, dpLeft[i] + dpRight[i] + 1);
        }
    }

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

• 时间复杂度分析： 三次独立的 $O(N)$ 遍历（一次求 dpLeft，一次求 dpRight，一次计算答案）。总体时间复杂度优化至 $O(N)$。可以轻松通过 $N = 10^5$ 的数据，拿到满分。
• 空间复杂度分析： 额外开辟了 dpLeft 和 dpRight 两个数组，辅助空间复杂度为 $O(N)$。

版本三：最优双指针/状态机版 (极致空间优化)

思路： 我们真的需要预存所有点的上坡和下坡长度吗？不需要！ 我们可以用一个指针 base 记录山脚。只要遇到上坡，我们就顺着爬到山峰（peak），然后再顺着走到右山脚（end）。算完这座山的长度后，直接让 base = end（因为这座山的右脚，完全可能紧接着是下一座山的左脚！）。这样只需扫一遍数组即可。

#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 < 3) {
        cout << 0 << "\n";
        return 0;
    }

    int ans = 0;
    int base = 0; // 记录每座山的左山脚

    // 只要山脚还没到数组末尾，就继续找
    while (base < n - 1) {
        int end = base;
        
        // 1. 寻找山峰：尝试向上爬
        // 必须保证没越界，并且是严格递增
        while (end + 1 < n && a[end] < a[end + 1]) {
            end++;
        }
        
        // 【关键点】判断是否真正爬了坡。如果 end 还是等于 base，说明一开始就是下坡或平地
        if (end > base) {
            int peak = end; // 记录山峰位置
            
            // 2. 寻找右山脚：尝试向下走
            // 必须保证没越界，并且是严格递减
            while (end + 1 < n && a[end] > a[end + 1]) {
                end++;
            }
            
            // 【关键点】判断是否真正下了坡。只有既上坡又下坡，才是真正的山
            if (end > peak) {
                // 计算当前山的长度，并更新最大值
                ans = max(ans, end - base + 1);
            } else {
                // 如果只上坡没下坡（比如一直递增到了数组末尾），或者遇到平坡了
                // 此时无法形成山，直接跳过。
            }
        }
        
        // 3. 移动 base 指针到下一个潜在的山脚
        // 【易错点优化】如果 base 和 end 相等（说明遇到了平坡或开局下坡没走动），为了防止死循环，强制推进一步
        // 如果 end 走动了，那么下一座山的左山脚恰好可以是当前山的右山脚，直接赋值即可
        base = max(end, base + 1);
    }

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

• 时间复杂度分析： 尽管代码里有嵌套的 while 循环，但你仔细观察指针 base 和 end 的运动轨迹：它们是永远不回头的（单调递增）。每个元素最多被作为上坡或下坡被访问两次。因此，摊还分析下的时间复杂度为绝对的 $O(N)$。常数极小，运行飞快。
• 空间复杂度分析： 除了输入数组 a 之外，只使用了几个整型变量 base, end, peak, ans。额外空间复杂度压缩到了完美的 $O(1)$。

教练总结

对比上一题的 “Min-Max 模式”，今天的 “Trend-Based 模式” 有一个本质的不同：状态的脆弱性。

• 找最大值/最小值时，历史最值是可以无条件“继承”的（所以可以用前缀和）。
• 找趋势长度时，一旦遇到平路或者反向，积累的长度必须无情地清零。

所以在写 DP 转移方程或者 while 循环时，一定要时刻警惕 =（相等，即平坡） 这种情况。平坡既不是上坡也不是下坡，是截断山脉的头号杀手！在 NOI 中，出题人极大概率会在测试数据里放大量形如 [2, 2, 2] 或者 [1, 2, 2, 3] 的数据来卡错你的程序。掌握了上面的版本三，你就再也不怕这类陷阱了！