fork download
copy 
  1. def MaxCross(A,low,mid,high):
  2.     left_sum=-100000
  3.     sum=0
  4.     for i in range(low,mid+1,1):
  5.         sum=sum+A[i]
  6.         if(sum>left_sum):
  7.             left_sum=sum
  8.             max_left=i
  9.     right_sum=-100000
  10.     sum=0
  11.     for j in range(mid+1,high+1,1):
  12.         sum=sum+A[j]
  13.         if(sum>right_sum):
  14.             right_sum=sum
  15.             max_right=j
  16.     return (max_left,max_right,left_sum+right_sum)
  17.  
  18. def MaxSum(A,low,high):
  19.     if(high==low):
  20.         return (low,high,A[low])
  21.     else:
  22.         mid=(low+high)//2
  23.         (left_low,left_high,left_sum)=MaxSum(A,low,mid)
  24.         (right_low,right_high,right_sum)=MaxSum(A,mid+1,high)
  25.         (cross_low,cross_high,cross_sum)=MaxCross(A,low,mid,high)
  26.         if(left_sum>=right_sum and left_sum>=cross_sum):
  27.             return (left_low,left_high,left_sum)
  28.         if(right_sum>=left_sum and right_sum>=cross_sum):
  29.             return (right_low,right_high,right_sum)
  30.         else:
  31.             return (cross_low,cross_high,cross_sum)
  32.  
  33. A=[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22]
  34. t=MaxSum(A,0,12)
  35. print(t)
  36.  
Success #stdin #stdout 0.01s 28384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(0, 10, 56)
https://ideone.com/7YS8OT
language:
Python 3 (python  3.9.5)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!