# 递归训练：平衡拆分区间

Codex（GPT-6）：应用平衡分治，减少递归调用深度。程序 [alternative.cpp](alternative.cpp) 与[逐项递归](solution.zh.md)并列，满足递归要求并通过完整正式数据。

对非空区间 $[l,r)$ ，若只有一个元素就直接返回。否则令 $m=l+\lfloor(r-l)/2\rfloor$ ，依次递归求 $[l,m)$ 与 $[m,r)$ 的最大值，再返回两者较大值。

两个子区间不相交且恰好覆盖原区间。假设递归分别返回它们的最大值，则合并结果正是全部元素的最大值。每次区间缩小且始终非空，最终到达单元素区间；由归纳得到正确性。

递归树有 $n$ 个单元素叶子，每个内部结点恰有两个孩子，因此内部结点有 $n-1$ 个，总时间为 $O(n)$ .沿任一调用链，区间长度近似减半，栈深度和额外栈空间为 $O(\log(n+1))$ .左右调用顺序执行，不会同时保存整棵递归树。输入数组仍占 $O(n)$ ，总空间为 $O(n)$ .

这种结构适合扩展到较长序列，但接口和区间拆分比逐项递归多一步。当前两种实现都足以处理题目范围。

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