def MaxCross(A,low,mid,high):
left_sum=-100000
sum=0
for i in range(low,mid+1,1):
sum=sum+A[i]
if(sum>left_sum):
left_sum=sum
max_left=i
right_sum=-100000
sum=0
for j in range(mid+1,high+1,1):
sum=sum+A[j]
if(sum>right_sum):
right_sum=sum
max_right=j
return (max_left,max_right,left_sum+right_sum)
def MaxSum(A,low,high):
if(high==low):
return (low,high,A[low])
else:
mid=(low+high)//2
(left_low,left_high,left_sum)=MaxSum(A,low,mid)
(right_low,right_high,right_sum)=MaxSum(A,mid+1,high)
(cross_low,cross_high,cross_sum)=MaxCross(A,low,mid,high)
if(left_sum>=right_sum and left_sum>=cross_sum):
return (left_low,left_high,left_sum)
if(right_sum>=left_sum and right_sum>=cross_sum):
return (right_low,right_high,right_sum)
else:
return (cross_low,cross_high,cross_sum)
A=[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22]
t=MaxSum(A,0,12)
print(t)
ZGVmIE1heENyb3NzKEEsbG93LG1pZCxoaWdoKToKICAgIGxlZnRfc3VtPS0xMDAwMDAKICAgIHN1bT0wCiAgICBmb3IgaSBpbiByYW5nZShsb3csbWlkKzEsMSk6CiAgICAgICAgc3VtPXN1bStBW2ldCiAgICAgICAgaWYoc3VtPmxlZnRfc3VtKToKICAgICAgICAgICAgbGVmdF9zdW09c3VtCiAgICAgICAgICAgIG1heF9sZWZ0PWkKICAgIHJpZ2h0X3N1bT0tMTAwMDAwCiAgICBzdW09MAogICAgZm9yIGogaW4gcmFuZ2UobWlkKzEsaGlnaCsxLDEpOgogICAgICAgIHN1bT1zdW0rQVtqXQogICAgICAgIGlmKHN1bT5yaWdodF9zdW0pOgogICAgICAgICAgICByaWdodF9zdW09c3VtCiAgICAgICAgICAgIG1heF9yaWdodD1qCiAgICByZXR1cm4gKG1heF9sZWZ0LG1heF9yaWdodCxsZWZ0X3N1bStyaWdodF9zdW0pCgpkZWYgTWF4U3VtKEEsbG93LGhpZ2gpOgogICAgaWYoaGlnaD09bG93KToKICAgICAgICByZXR1cm4gKGxvdyxoaWdoLEFbbG93XSkKICAgIGVsc2U6CiAgICAgICAgbWlkPShsb3craGlnaCkvLzIKICAgICAgICAobGVmdF9sb3csbGVmdF9oaWdoLGxlZnRfc3VtKT1NYXhTdW0oQSxsb3csbWlkKQogICAgICAgIChyaWdodF9sb3cscmlnaHRfaGlnaCxyaWdodF9zdW0pPU1heFN1bShBLG1pZCsxLGhpZ2gpCiAgICAgICAgKGNyb3NzX2xvdyxjcm9zc19oaWdoLGNyb3NzX3N1bSk9TWF4Q3Jvc3MoQSxsb3csbWlkLGhpZ2gpCiAgICAgICAgaWYobGVmdF9zdW0+PXJpZ2h0X3N1bSBhbmQgbGVmdF9zdW0+PWNyb3NzX3N1bSk6CiAgICAgICAgICAgIHJldHVybiAobGVmdF9sb3csbGVmdF9oaWdoLGxlZnRfc3VtKQogICAgICAgIGlmKHJpZ2h0X3N1bT49bGVmdF9zdW0gYW5kIHJpZ2h0X3N1bT49Y3Jvc3Nfc3VtKToKICAgICAgICAgICAgcmV0dXJuIChyaWdodF9sb3cscmlnaHRfaGlnaCxyaWdodF9zdW0pCiAgICAgICAgZWxzZToKICAgICAgICAgICAgcmV0dXJuIChjcm9zc19sb3csY3Jvc3NfaGlnaCxjcm9zc19zdW0pCgpBPVsxMywtMywtMjUsMjAsLTMsLTE2LC0yMywxOCwyMCwtNywxMiwtNSwtMjJdCnQ9TWF4U3VtKEEsMCwxMikKcHJpbnQodCkK