写出分治查找最大值位置的算法

下面是分治查找最大值位置的算法：

1. 将数组分成两半，找到中间位置mid，分别在左半部分和右半部分递归查找最大值位置。

2. 在左半部分和右半部分中找到最大值的位置maxLeft和maxRight。

3. 比较maxLeft和maxRight，返回较大值所在的位置。

4. 如果左半部分和右半部分的最大值都小于等于中间位置mid的值，则mid为最大值所在的位置。

5. 如果数组为空，则返回-1表示未找到最大值。

下面是该算法的Python实现：

def findMax(arr, left, right):
    if left == right:
        return left
    mid = (left + right) // 2
    maxLeft = findMax(arr, left, mid)
    maxRight = findMax(arr, mid+1, right)
    if arr[maxLeft] > arr[maxRight]:
        return maxLeft
    else:
        return maxRight

arr = [3, 5, 1, 7, 9, 4, 8, 2, 6]
index = findMax(arr, 0, len(arr)-1)
print("The index of maximum element is", index)

输出结果为：

The index of maximum element is 4

说明最大值7在数组的第5个位置。