def MaxCrossSubarray(num,mid,low,high):
leftsum=
0
leftmax=-1000000
rightsum=
0
rightmax=-1000000
for i
in range(mid,low-1,-1
):
leftsum=leftsum+
num[i]
if leftsum>
leftmax:
leftmax=
leftsum
leftlow=
i
for j
in range(mid+1,high+1
):
rightsum=rightsum+
num[j]
if rightsum>
rightmax:
rightmax=
rightsum
righthigh=
j
sum=leftmax+
rightmax
return (leftlow,righthigh,sum)
def MaxSubarray(num,low,high):
if low==
high:
return (low,high,num[low])
else:
mid=(low+high)//2
(left_low,left_high,left_sum)=
MaxSubarray(num,low,mid)
(right_low,right_high,right_sum)=MaxSubarray(num,mid+1
,high)
(cross_low,cross_high,cross_sum)=
MaxCrossSubarray(num,mid,low,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)
elif(cross_sum>left_sum
and cross_sum>
right_sum):
return (cross_low,cross_high,cross_sum)
a=[13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7
]
max = MaxSubarray(a, 0, len(a)-1
)
print max
转载于:https://www.cnblogs.com/mactep/p/6872727.html
