你好！我是你的OI教练。这张图片继续深入了“左右模式变化”（Left-Right Pattern Variations）这一大类经典的线性预处理技巧。

这次你圈出的是红框中的 Trend-Based（基于趋势） 模式。相比于上一次的 Min-Max 找极值，这次我们找的是连续的单调区间长度。

为了让你更好地在NOI体系中掌握这个考点，我们按照老规矩，先看题，再拿草稿纸一步步推导，最后画流程图。

1. NOI风格模拟试题

题目名称： 数组中最长的山 (Longest Mountain in Array)

题目描述： 给定一个长度为 $N$ 的整数数组 $A$。 我们定义一个子数组（即数组中连续的一段）为“山脉子数组”，当且仅当它满足以下条件：

1. 子数组的长度大于等于 $3$。
2. 存在一个中间的“山峰”元素，使得它左边的元素严格单调递增，右边的元素严格单调递减。 更正式地说，存在一个下标 $i$（$0 < i < \text{长度}-1$），使得 $B_0 < B_1 < \dots < B_i$ 且 $B_i > B_{i+1} > \dots > B_{\text{长度}-1}$。

请你编写一个程序，找出数组 $A$ 中最长的山脉子数组，并输出其长度。如果数组中不存在山脉子数组，则输出 $0$。

输入格式： 第一行包含一个整数 $N$ $(1 \le N \le 10^5)$，表示数组的长度。 第二行包含 $N$ 个由空格隔开的整数 $A_i$ $(0 \le A_i \le 10^4)$。

输出格式： 输出一个整数，表示最长的山脉子数组的长度。如果没有符合条件的子数组，输出 $0$。

样例输入：

7
2 1 4 7 3 2 5

样例输出：

5

样例说明： 最长的山脉子数组是 1 4 7 3 2，长度为 $5$。其中 $7$ 是山峰。

2. 预备知识点总结

攻克这类“趋势”题，你需要具备以下预备知识：

• 子数组与子序列的区别： “子数组（Subarray）”必须是原数组中连续的一段；而“子序列（Subsequence）”可以是不连续的。这决定了我们在状态转移时，一旦不满足条件，长度就要立刻清零。
• 线性动态规划（Linear DP）： 学会定义一维状态数组，用来记录“以当前元素为结尾（或开头）的某种状态”。
• 左右双向预处理（Two-pass Arrays）： 能够熟练地正向遍历一次处理左侧依赖，反向遍历一次处理右侧依赖。

3. 启发式教学：草稿纸上的推理过程

同学们，拿起草稿纸，把样例数据 [2, 1, 4, 7, 3, 2, 5] 写下来。

第一步：暴力思考法（如何识别一座山？）

如果要用最暴力的方法，我们会枚举每一个元素作为“山峰”，然后向左扩展看能严格递减延伸多远，向右扩展看能严格递减延伸多远。

• 教练提问： 这样做复杂度是多少？
• 思考回答： 枚举山峰需要 $O(N)$，向左向右扩展在最坏情况下（比如单调递增再单调递减的长数组）每次也需要 $O(N)$。总时间复杂度是 $O(N^2)$，对于 $N=10^5$ 会超时。

第二步：引入 Trend-Based 模式（化 $O(N^2)$ 为 $O(N)$）

看红框里的提示： dpLeft: 递增子数组的长度（从左到右）。 dpRight: 递减子数组的长度（从右到左）。

我们在草稿纸上画三个数组格子，一步步填：

1. 原始数组 A: [ 2, 1, 4, 7, 3, 2, 5 ]
2. 构建 dpLeft (左侧上坡长度):
   • 含义：dpLeft[i] 表示以 $A_i$ 结尾的、连续严格递增的子数组长度（不含自己）。如果 $A_i > A_{i-1}$，则 dpLeft[i] = dpLeft[i-1] + 1；否则是 $0$。
   • 手推一下：从左向右看。
     • 2: 前面没东西，0。
     • 1: $1 \le 2$，没爬坡，0。
     • 4: $4 > 1$，爬坡，dpLeft 为前面加一，变成 1。
     • 7: $7 > 4$，爬坡，dpLeft 为前面加一，变成 2。
     • 后续... 推导得出：[ 0, 0, 1, 2, 0, 0, 1 ]。
3. 构建 dpRight (右侧下坡长度):
   • 含义：dpRight[i] 表示以 $A_i$ 开头的、连续严格递减的子数组长度（不含自己）。如果 $A_i > A_{i+1}$，则 dpRight[i] = dpRight[i+1] + 1；否则是 $0$。
   • 手推一下：从右向左看！
     • 5: 后面没东西，0。
     • 2: $2 \le 5$，没下坡，0。
     • 3: $3 > 2$，下坡，dpRight 为右边加一，变成 1。
     • 7: $7 > 3$，下坡，dpRight 为右边加一，变成 2。
     • 后续... 推导得出：[ 1, 0, 0, 2, 1, 0, 0 ]。

教练引导核心： 现在，假设 $A_i$ 是一座山的“山峰”，那么这整个山的长度是多少？ 显然是：左边的上坡长度 + 右边的下坡长度 + 山峰自己（1），也就是 dpLeft[i] + dpRight[i] + 1。

致命易错点： 一座山必须既有上坡也有下坡！如果只有上坡（比如走到尽头了）或者只有下坡，不能称为山。 所以在统计答案时，必须满足 dpLeft[i] > 0 且 dpRight[i] > 0 才能计算为一座山。

在我们的样例中，山峰为 $7$ （下标3）时，dpLeft[3]=2, dpRight[3]=2，都大于0。计算总长 $2 + 2 + 1 = 5$。最大值就是5。

第三步：伪代码流程图设计

理清逻辑后，我们用流程图写下 NOI 标准的伪代码逻辑（已规避特殊字符报错风险）：

graph TD
    A(开始) --> B(读取数组大小 N 和 数组 A)
    B --> C{N 是否小于 3}
    C -- 是 --> D(直接输出 0 并结束)
    C -- 否 --> E(创建 dpLeft 和 dpRight 数组并初始化为 0)
    E --> F(循环 i 从 1 到 N减1)
    F --> G{A的第i项 是否大于 A的第i减1项}
    G -- 是 --> H(dpLeft第i项 等于 dpLeft第i减1项 加 1)
    G -- 否 --> I(dpLeft第i项 保持为 0)
    H --> J(继续下一个 i 循环直到结束)
    I --> J
    J --> K(循环 i 从 N减2 递减到 0)
    K --> L{A的第i项 是否大于 A的第i加1项}
    L -- 是 --> M(dpRight第i项 等于 dpRight第i加1项 加 1)
    L -- 否 --> N(dpRight第i项 保持为 0)
    M --> O(继续下一个 i 循环直到结束)
    N --> O
    O --> P(初始化 最大长度 ans 为 0)
    P --> Q(循环 i 从 1 到 N减2)
    Q --> R{判断 dpLeft第i项 大于 0 并且 dpRight第i项 大于 0}
    R -- 是 --> S(更新 ans 为 ans 和 dpLeft第i项加dpRight第i项加1 之间的最大值)
    R -- 否 --> T(跳过当前项)
    S --> U(继续下一个 i 循环直到结束)
    T --> U
    U --> V(输出 最大长度 ans)
    V --> W(结束)

第四步：复杂度分析与极致优化思考

• 当前时间复杂度： 循环了三次（一次正向求 left，一次反向求 right，一次求最大值），每次都是 $O(N)$。常数相加，总体时间复杂度为 $O(N)$。
• 当前空间复杂度： 开设了 dpLeft 和 dpRight 两个长度为 $N$ 的数组，空间复杂度为 $O(N)$。

教练的时间/空间复杂度优化建议： 虽然 $O(N)$ 空间完全能拿满分，但我们要追求卓越。这题能把空间优化到 $O(1)$ 吗？ 答案是可以的。 不需要提前存好所有的左侧和右侧长度。你可以使用 “双指针”或“状态机” 的思想： 只用一次从左到右的遍历 $O(N)$。用一个指针 $i$ 找山脚。找到山脚后，用内层 while 循环不断向上爬，记录上坡长度；到达巅峰后，再用 while 循环向下走，记录下坡长度。走完后更新最大答案，并将起始位置移动到当前的右山脚。 这样，连额外的数组都不需要开，不仅空间变成了 $O(1)$，常数也更小，因为每个元素最多被访问两次。

4. 读题技巧：此类题型的关键词在哪里？

遇到这类题，养成对以下字眼的敏感度：

1. “连续的” / “子数组” / “子串”： 这要求状态具有连续性。一旦不满足趋势（比如平坡 $A_i == A_{i-1}$，或者反向了），状态计数器必须立刻清零，而不是像“子序列”那样继承前面的最大值。
2. “单调递增再单调递减” / “波峰波谷”： 这明确暗示了你需要维护两种相反的趋势统计。往往需要引入两个数组（左往右扫一遍，右往左扫一遍），或者使用包含“上升态”和“下降态”的状态机去解决。
3. “最长的...”： 这意味着在遍历所有可能的中心点（山峰）时，用一个全局变量 ans = max(ans, current_len) 不断更新极值。

思路理清了，你现在可以尝试自己把 C++14 的代码落实下来了。注意处理平坡（相邻元素相等）导致的山脉断裂哦！