A101156.求区间最大值（填空题）

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\dots,a_n$。请你使用分治递归计算整个数组的最大值。

分治思想：把区间 $[l,r]$ 拆成左右两半 $[l,mid]$ 与 $[mid+1,r]$，分别递归求最大值，再合并答案。

具体例子

• 若 $a=[2,7,1,5]$，可拆成 $[2,7]$ 与 $[1,5]$：左半最大为 $7$，右半最大为 $5$，合并得到整体最大为 $7$。
• 若区间只有一个数（例如 $[l,l]$），该区间最大值就是这个数本身。

第一行包含一个整数 $n$。
第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出一行一个整数，表示数组最大值。

数据范围

• $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$。

合并得到

$$\max([4,5])=\max(9,3)=9.$$

---

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

把左半与右半合并：

$$\max([1,5])=\max(\max([1,3]),\max([4,5]))=\max(7,9)=9.$$

因此输出为 $9$。