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.
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.
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
double the array and apply kadanes algorithm.
This might help…
7 Likes