分治策略之最大子数组问题

Posted on |

最大子数组

思路

使用分治策略意味着将子数组划分为两个规模尽量相等的子数组。也就是说需要找到子数组的中央位置mid。数组A[low…high]的任何连续子数组或最大子数组A[i…j]所处的位置必然是一下三种情况之一：

  • 完全位于左子数组A[low…mid]中
  • 完全位于右子数组A[mid+1…high]中
  • 跨越了中点

A[low…high]的一个最大子数组必然是完全位于左子数组中，完全位于右子数组中或者跨越中点的所有子数组中的和最大者。

  • 递归求解A[low…mid]和A[mid+1…high]的最大子数组（仍然是最大子数组问题，只是规模更小）
  • 寻找跨越中点的最大子数组
  • 然后在三种情况中选取和最大者

    Python实现

    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
    37
    38
    def FindMaxCrossingSubarray(A,low,mid,high):
        left_sum=float('-inf')
        sum=0
        for i in range(mid,low-1,-1):
            sum=sum+A[i]
            if sum>left_sum:
                left_sum=sum
                max_left=i
        right_sum=float('-inf')
        sum=0
        for i in range(mid+1,high+1):
            sum=sum+A[i]
            if sum>right_sum:
                right_sum=sum
                max_right=i
        return (max_left,max_right,left_sum+right_sum)

    def FindMaxSubarray(A,low,high):
        if high==low:
            return (low,high,A[low])
        else:
            mid=int((low+high)/2)
            (left_low,left_high,left_sum)=FindMaxSubarray(A,low,mid)
            (right_low,right_high,right_sum)=FindMaxSubarray(A,mid+1,high)
            (cross_low,cross_high,cross_sum)=FindMaxCrossingSubarray(A,low,mid,high)
            if left_sum>=right_sum and left_sum >=cross_sum:
                return (left_low,left_high,left_sum)
            elif right_sum>=left_sum and right_sum>=cross_sum:
                return (right_low,right_high,right_sum)
            else:
                return (cross_low,cross_high,cross_sum)


    if __name__=='__main__':
        import random
        A=[random.randrange(-10,20) for i in range(5)]
        print ('Input:\t',A)
        print('Output:\t',FindMaxSubarray(A,0,len(A)-1))

时间复杂度分析

A[low…high]中包含n个元素（n=high-low+1），调用FindMaxCrossingSubarray(A,low,mid,high)花费时间$\Theta(n)$。
两个for循环的每次迭代花费时间$O(1)$，只需要统计执行的循环次数。

  • 第一个for循环，迭代了$mid-low+1$次
  • 第二个for循环，迭代了$high-mid$次
    因此，总的迭代次数是$mid-low+1+high-mid=high-low+1=n$

建立递归式描述过程FindMaxSubarray的运行时间。

  • 第一行花费常量时间
  • 对于n=1时为基本情况，第二行花费常量时间，$T(1)=O(1)$
  • 对于n>1时为递归情况，第1行和第4行花费常量时间，第5和6行求解左右子数组问题花费$2T(n/2)$，第7行调用FindMaxCrossingSubarry花费时间$\Theta(n)$,第8-12行花费时间$O(1)$