How to do in circular

#1

How do i do that for circular? By creating new array??

#2

I am assuming you already know how to calculate the same for a non circular array. Now, imagine if our answer is a subarray that does not go round i.e. the maximum sum subarray is just a linear piece of array then we can simply apply the kadane’s algorithm on this array to find this value. Now, the second case arises, is that the answer subarray involves some elements from end and then wraps back to 1st element and some elements from the start. Now, in this case, the elements that are not counted in our answer subarray form a linear piece without wrapping. And these non contributing elements infact form the minimum subarray sum. To find this subarray, just invert the sign of all the elements and run kadane’s algorithm on the array again. Now, subtract this value from the total sum. Report the maximum of case 1 and case 2 as answer.

#3

As we are taking 2 cases separeately i.e wrapped and non wrapped we dont need to account for the case when all nos are neagative , right?

#4

No need to do that______

#5

Why are we inverting the signs and taking two cases can’t we just use kadane to find mind and subtract that from total sum

#6

Also in the method that you suggested how are we accounting for cases like , {-1,-3,-2}, according to your approach till will give us 0 , but the answer should be -1??

#7

If all the elements are negative, you can separately handle that case, and for your second query, I don’t see how we can calculate minimum sum subarray simply

#8

No, I am sorry, you can actually find that out by modifying kadane.