I understood the concept of the maximum subarray problem(using divide and conquer). But I’m afraid that I wrote it wrong and the time complexity is still O(n^square). I understood that i have divide to divide the array into two halves and then check for the maximum sum in the left part, right part and at the centre crossing subarray too. Can anyone tell me the time complexity? I think its O(n^2)
def maxcross(l,r,arr):
mid=(l+r)//2
left_sum=-4567
sum=0
for i in range(mid,-1,-1):
sum+=arr[i]
if sum>left_sum:
sum=left_sum
right_sum=-4748
sum=0
for j in range(mid+1,r):
sum+=arr[j]
if sum>right_sum:
sum=right_sum
return right_sum+left_sum
def maxsubarray(l,r,arr):
if l==r:
return arr[l]
else:
mid=(l+r)//2
left=-8992
sum=0
for i in range(0,mid):
sum+=arr[i]
if sum>left:
sum=left
right=-3883
sum=0
for j in range(mid,r):
sum+=arr[j]
if sum>right:
right=sum
return max(left,right,maxcross(l,r,arr))
arr=[int(x) for x in input().split()]
print(maxsubarray(0,len(arr)-1,arr))