问题描述：
给定一个包含 n 个整数的数组，找到数组中的最大值。要求使用分治法进行求解。
分析：
分治法是一种将问题划分为小规模子问题的算法，通过递归的方式求解子问题，并将结果合并为原问题的解。对于求数组最大值的问题，我们可以采用分治法将其划分为两个子问题，分别求解左半部分的最大值和右半部分的最大值，然后返回两个最大值中的较大值。
证明：
为了证明上述算法的正确性，我们需要证明以下两点：
递归的终止条件是正确的。当 left == right 时，数组中只有一个元素，直接返回该元素的值即可。当 right - left == 1 时，数组中只有两个元素，返回其中较大的一个即可。
在每一次递归中，我们能够正确地计算出左半部分和右半部分的最大值，并将它们返回。由于每一次递归都是对原问题规模的一半进行求解，因此在最坏情况下，递归树的深度为 O(log n)。
代码：
以下是上述算法的实现代码：
#include <bits/stdc++.h>
using namespace std;
int div_max(vector<int>& nums, int left, int right) {
if (left == right) {
return nums[left];
} else if (right - left == 1) {
return max(nums[left], nums[right]);
}
int mid = left + ((right - left) >> 1);
int max_left = div_max(nums, left, mid);
int max_right = div_max(nums, mid + 1, right);
return max(max_left, max_right);
}
int main() {
vector<int> nums = {4, 7, 6, 5, 4, 3, 2};
cout << div_max(nums, 0, nums.size() - 1) << endl; // 注意这里应该使用 nums.size() - 1 作为右边界
return 0;
}
解释：
上述代码中，我们首先判断当前子数组的规模是否为 1 或 2，如果是，则直接返回其中的最大值。否则，我们计算出当前子数组的中间位置 mid，并递归求解左半部分的最大值 max_left 和右半部分的最大值 max_right，最后返回它们中的较大值。
复杂度分析：
上述算法的时间复杂度为 O(log n)，其中 n 是数组的长度。这是因为在每一次递归中，我们都是将原问题的规模缩小一半，因此递归树的深度为 O(log n)。由于在每一次递归中都需要计算最大值，因此时间复杂度为 O(n)。但由于递归树深度较浅，因此总的时间复杂度为 O(n log n)。空间复杂度为 O(log n)，因为递归过程中需要使用到栈空间。