chap4 分治策略

最大子数组 分治策略 算法导论

内容

最大子数组问题

1. 给定一个数组，返回该数组中和最大的非空连续子数组
2. 由于计算子数组的过程可以被重复利用，因而可以使用分治策略来节约时间节约时间
3. 运行时间$\Theta \left ( n\lg n \right )$

伪代码

最大子数组问题

FindMaximumSubarray(A,low,high)

if low = high
    return (low,high,A[low])
else
    mid = (low + high)/2 #向下取整
    (left_low,left_high,left_sum) = FMS(A,low,mid)
    (right_low,right_high,right_sum) = FMS(A,mid+1,high)
    (cross_low,cross_high,cross_sum) = FMCS(A,low,mid,high)
if left_sum >= right_sum && left_sum >= cross_sum
    return ((left_low,left_high,left_sum))
else if right_sum >= left_sum && right_sum >= cross_sum
    return (right_low,right_high,left_sum)
else
    return (cross_low,cross_high,cross_sum)

#寻找横跨中点的最大子数组
FindMaxCrossSubarray(A,low,mid,high)

left_sum = right_sum = -inf
#寻找左边的最大连续子数组
sum = 0
for i = mid down to low
    sum += A[i]
    if sum > left_sum
        left_sum = sum
        max_left = i #记录左边端点位置
#寻找右边的最大连续子数组
sum = 0
for j = mid+1 to high
    sum += A[j]
    if sum > right_sum
        right_sum = sum
        max_right = j #记录右边端点位置
return (max_left,max_right,left_sum+right_sum)

代码实现

• java