python——分治策略求最大值和最小值_分治算法最小值问题 算法分析ph

最近在学算法，刚入手分治，这是自己的一些心得，记录一下。

分治就是把一个大的问题分成很多小的子问题，不断调用递归将问题分解成多个小问题。以下是个人解题的一些想法：

1. 分治其实就是递归的一种用途，必须要有递归出口，就是当问题小到一定程度我们可以解决了，可以每次考虑从出口入手问题。
2. 分治是先分再合，分完后记得还要将问题的解和起来

代码实现

def maxmin(l, low, high):
    #   判断列表分到最后只剩下一个或者两个数时就比较
    #   返回的是一个列表[max,min]，第一个最大值，第二个最小值
    if high - low <= 1:
        if l[low] < l[high]:
            return [l[high], l[low]]
        else:
            return [l[low], l[high]]
    # 选取分治的中点
    mid = (low + high) // 2
    # 调用递归
    left_list = maxmin(l, low, mid)
    right_list = maxmin(l, mid + 1, high)
    # 将左边的最大值和右边的最大值比较
    if left_list[0] > right_list[0]:
        # 将左边的最小值和右边最小值比较
        if left_list[1] > right_list[1]:
            # 返回列表[max,min]
            return [left_list[0], right_list[1]]
        else:
            return [left_list[0]