# 递归训练：逐项合并最大值

出题人解法：递归求前缀最大值，再与末项比较。Codex（GPT-6）：整理区间接口和边界证明，并补充降低调用深度的平衡递归方案。

## 首选递归

使用零起始、左闭右开的区间 $[l,r)$ .若 $r-l=1$ ，返回唯一元素；否则返回

$$M(l,r)=\max\{M(l,r-1),a_{r-1}\}$$

初始调用 $M(0,n)$ .数组通过常量引用传递，不在每层复制。

当区间只有一个元素时返回值正确。长度更大时，前 $r-l-1$ 项的最大值由递归正确求出，与最后一项取最大即得到整个区间最大值。对区间长度归纳可证答案正确。返回实际元素而非零，保证全负数输入正确。

## 代价与递归要求

有 $n$ 次递归调用、$n-1$ 次比较，时间 $O(n)$ .调用链最多 $n$ 层，栈空间 $O(n)$ ；保存输入数组后总空间仍为 $O(n)$ .本题 $n\le100$ ，该深度适用。

[std.cpp](std.cpp) 用递归返回值参与最大值计算，满足实现要求。单看输出无法验证递归，因此使用本题作训练时还须检查源代码。

[平衡区间递归](solution-alternative.zh.md)和 [alternative.cpp](alternative.cpp)把调用深度降为 $O(\log(n+1))$ ，保留 $O(n)$ 总时间。它有明确的辅助栈优势，作为并列方案；两者的输入数组都占 $O(n)$ ，不能把平衡方案的总空间写成对数。两份程序均通过完整正式数据。

测试配方见 [plan.json](tests/plan.json)，生成方式见[数据生成说明](../../../README.md#使用题目文件)。参考环境、逐次测量和适用范围见[评测说明](../../../docs/评测环境与性能.md)。