@zqbinggong
2018-03-06T21:37:05.000000Z
字数 876
阅读 926
最大子数组
分治策略
算法导论
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)