d+ sum sub style max sss log oss
- def MaxCrossSubarray(num,mid,low,high):
- leftsum=0
- leftmax=-1000000
- rightsum=0
- rightmax=-1000000foriinrange(mid,low-1,-1):
- leftsum=leftsum+num[i]
- ifleftsum>leftmax:
- leftmax=leftsum
- leftlow=i
- forjinrange(mid+1,high+1):
- rightsum=rightsum+num[j]
- ifrightsum>rightmax:
- rightmax=rightsum
- righthigh=j
- sum=leftmax+rightmax
- return (leftlow,righthigh,sum)
- def MaxSubarray(num,low,high):
- iflow==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_sumandleft_sum>cross_sum):
- return (left_low,left_high,left_sum)
- elif(right_sum>left_sumandright_sum>cross_sum):
- return (right_low,right_high,right_sum)
- elif(cross_sum>left_sumandcross_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)
- printmax
使用分治算法求解最大子数组问题
来源: http://www.bubuko.com/infodetail-2075868.html