分治算法初步

例：

最大子数组的差问题。

给定数组[13,-3,-25,20,-3,-16,-23, …],
求数组中连续的首尾差最大的子数组。

对于A[low, high),划分为A[low,mid), A[mid, high)

此时最大子数组只可能有三种情况：

  • 完全位于A[low, mid)

  • 完全位于A[mid, high)

  • 横跨中点

我们可以递归求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def calculate_mid(A, low, high):
    m = (low+high)//2
    minnum = A[m]
    maxnum = A[m]
    mlow = m
    mhigh = m
    for i in range(low, m):
        if A[i] < minnum:
            minnum = A[i]
            mlow = i
    for i in range(m,high):
        if A[i] > maxnum:
            maxnum = A[i]
            mhigh = i
    return maxnum-minnum, mlow, mhigh

def f(A, low, high):
    if low == high:
        return 0, low, high
    if low + 1 == high:
        if high >= len(A):
            return 0, low, high
        return A[high]-A[low], low, high
        
    else:
        left, llow, lhigh = f(A, low, (low+high)//2)
        right, rlow, rhigh = f(A, (low+high)//2, high)
        mid, mlow, mhigh = calculate_mid(A, low, high)
        max_cha = max(left, right, mid)

        if max_cha == left:
            return max_cha, llow, lhigh
        elif max_cha == right:
            return max_cha, rlow, rhigh
        else:
            return max_cha, mlow, mhigh

** 以上代码并非计算最大子数组的和 **

  • 算法导论提供另一种思路：

    1. 将每天相对于前一天的变化值记录下，作为新数组 – O(n)
    2. 计算最大子数组（即数组各元素和最大的子数组）

      计算子数组的和 与 计算首尾差 对算法实现并无太大影响。
      算法本质都是使用分治法。

  • 分治核心就是将大问题划分为多个小问题

  • 如计算最大子数组就是将问题划分为三个板块

    完全左半部分， 完全右半部分， 横跨中点。
    其中前两者都是递归。后者可遍历直接得出答案。