sir i am not able to understand one thing in the code that sir explained that in circular sum , we invert the elements of array for getting minimum sum of array and then subtracting it from the total sum of the original array .
but in the code in line 33 , we are adding them, so please explain me what’s happening there .
code -> https://ide.codingblocks.com/s/482517
Max circular sum subarray
no we have to add them
this is because the sum we get will be negative so we have to add them
Logic
There can be two cases for the maximum sum:
- 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, we change wrapping to non-wrapping. find out the sum of non-contributing elements and subtract this sum from the total sum. To find out the sum of non-contributions, invert the 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 in both cases and return the maximum of the two sums.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.