Test Cases Failed

#1

Where are mistakes in my code?

#2
#3

for these inputs
8
10 -3 -4 7 6 5 -4 -1
8
-1 40 -14 7 6 5 -4 -1

your ans comes
37 and 82 resp.
but correct ans is
23 and 52 resp.

you logic is not correct for all testcase
use kadane’s algorithm for maximum circular subarray here

#4

i have also used kadane algo…but i don’t know how to move around a circular loop…what condition i will use

#5

there can be two cases
Case 1: The elements that contribute to the maximum sum are arranged such that no wrapping is there. Examples: {-10, 2, -1, 5}, {-2, 4, -1, 4, -1}. In this case, Kadane’s algorithm will produce the result.

Case 2: The elements which contribute to the maximum sum are arranged such that wrapping is there. Examples: {10, -12, 11}, {12, -5, 4, -8, 11}. In this case,find out the sum of non contributing elements and subtract this sum from the total sum. To find out the sum of non contributing, invert sign of each element and then run Kadane’s algorithm.
Our array is like a ring and we have to eliminate the maximum continuous negative that implies maximum continuous positive in the inverted arrays.

Finally we compare the sum obtained by both cases, and return the maximum of the two sums.

#6

Can you explain your logic my one example ?

#7

Now i got it …Thanks

1 Like