def MaxCross(A,low,mid,high):
left_sum=-100000
sum=0
for i in range(mid,low-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)
ZGVmIE1heENyb3NzKEEsbG93LG1pZCxoaWdoKToKICAgIGxlZnRfc3VtPS0xMDAwMDAKICAgIHN1bT0wCiAgICBmb3IgaSBpbiByYW5nZShtaWQsbG93LTEsLTEpOgogICAgICAgIHN1bT1zdW0rQVtpXQogICAgICAgIGlmKHN1bT5sZWZ0X3N1bSk6CiAgICAgICAgICAgIGxlZnRfc3VtPXN1bQogICAgICAgICAgICBtYXhfbGVmdD1pCiAgICByaWdodF9zdW09LTEwMDAwMAogICAgc3VtPTAKICAgIGZvciBqIGluIHJhbmdlKG1pZCsxLGhpZ2grMSwxKToKICAgICAgICBzdW09c3VtK0Fbal0KICAgICAgICBpZihzdW0+cmlnaHRfc3VtKToKICAgICAgICAgICAgcmlnaHRfc3VtPXN1bQogICAgICAgICAgICBtYXhfcmlnaHQ9agogICAgcmV0dXJuIChtYXhfbGVmdCxtYXhfcmlnaHQsbGVmdF9zdW0rcmlnaHRfc3VtKQoKZGVmIE1heFN1bShBLGxvdyxoaWdoKToKICAgIGlmKGhpZ2g9PWxvdyk6CiAgICAgICAgcmV0dXJuIChsb3csaGlnaCxBW2xvd10pCiAgICBlbHNlOgogICAgICAgIG1pZD0obG93K2hpZ2gpLy8yCiAgICAgICAgKGxlZnRfbG93LGxlZnRfaGlnaCxsZWZ0X3N1bSk9TWF4U3VtKEEsbG93LG1pZCkKICAgICAgICAocmlnaHRfbG93LHJpZ2h0X2hpZ2gscmlnaHRfc3VtKT1NYXhTdW0oQSxtaWQrMSxoaWdoKQogICAgICAgIChjcm9zc19sb3csY3Jvc3NfaGlnaCxjcm9zc19zdW0pPU1heENyb3NzKEEsbG93LG1pZCxoaWdoKQogICAgICAgIGlmKGxlZnRfc3VtPj1yaWdodF9zdW0gYW5kIGxlZnRfc3VtPj1jcm9zc19zdW0pOgogICAgICAgICAgICByZXR1cm4gKGxlZnRfbG93LGxlZnRfaGlnaCxsZWZ0X3N1bSkKICAgICAgICBpZihyaWdodF9zdW0+PWxlZnRfc3VtIGFuZCByaWdodF9zdW0+PWNyb3NzX3N1bSk6CiAgICAgICAgICAgIHJldHVybiAocmlnaHRfbG93LHJpZ2h0X2hpZ2gscmlnaHRfc3VtKQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIHJldHVybiAoY3Jvc3NfbG93LGNyb3NzX2hpZ2gsY3Jvc3Nfc3VtKQoKQT1bMTMsLTMsLTI1LDIwLC0zLC0xNiwtMjMsMTgsMjAsLTcsMTIsLTUsLTIyXQp0PU1heFN1bShBLDAsMTIpCnByaW50KHQpCg==