Maximum circular subarray sum

general
,
1

Can somebody give it’s solution with proper explanation
Given n numbers (both +ve and -ve), arranged in a circle, find the maximum sum of consecutive numbers.

2

One possible idea: double the array and use the usual greedy algorithm for this array. You have to take care not to have a sum with more elements than the initial array.

3

I have used this approach. But it gives me wrong answer on some test cases.

here’s my code

def subarray(arr):
smCurr,smEnd=[0,0]
n=len(arr)
#end=(0,0)
prev=0
#count=0
for i in range(0,n):
#count+=1
#print(arr[i])
smEnd=smEnd+arr[i]
if smEnd<0:
prev=i
smEnd=0
continue
if smCurr<smEnd:
#end=" ".join([str(prev),str(i)])
#print("Ending test "+end)
#print("i = “+str(prev)+” j = "+str(i) + " "+str(i-prev) + " <= "+str((len(arr)//2)-1))

        if i-prev<=(len(arr)//2)-1:  
            smCurr=smEnd
        else:
            continue
        #print("Sum ending here "+str(smCurr))
return smCurr
4

double the array and apply kadanes algorithm.

5

This might help…

7 Likes