A7118 | 求区间最大值（填空题）

数据范围

• $1\le n\le 2\times 10^5$
• $-10^9\le a_i\le 10^9$



样例解释


数组为
$$ a_1=2,\ a_2=7,\ a_3=1,\ a_4=9,\ a_5=3. $$
我们要求区间 $[1,5]$ 的最大值。

第 $1$ 步： 取
$$ mid=\left\lfloor\frac{1+5}{2}\right\rfloor=3, $$
把 $[1,5]$ 分成 $[1,3]$ 与 $[4,5]$。

---



计算左半区间 $[1,3]$ 的最大值


对区间 $[1,3]$，取
$$ mid=\left\lfloor\frac{1+3}{2}\right\rfloor=2, $$
拆成 $[1,2]$ 与 $[3,3]$。

• 对区间 $[1,2]$，取
$$ mid=\left\lfloor\frac{1+2}{2}\right\rfloor=1, $$
拆成 $[1,1]$ 与 $[2,2]$。
- $[1,1]$ 只有一个数，因此最大值为 $a_1=2$。
- $[2,2]$ 只有一个数，因此最大值为 $a_2=7$。
- 合并得到
$$ \max([1,2])=\max(2,7)=7. $$

• 对区间 $[3,3]$，只有一个数，因此最大值为 $a_3=1$。

合并得到
$$ \max([1,3])=\max(\max([1,2]),\max([3,3]))=\max(7,1)=7. $$

---



计算右半区间 $[4,5]$ 的最大值


对区间 $[4,5]$，取
$$ mid=\left\lfloor\frac{4+5}{2}\right\rfloor=4, $$
拆成 $[4,4]$ 与 $[5,5]$。
• $[4,4]$ 只有一个数，因此最大值为 $a_4=9$。
• $[5,5]$ 只有一个数，因此最大值为 $a_5=3$。

最后合并得到整个区间 $[1,5]$ 的最大值