Logic behind the algo used

#1

to find maximum circular subarray sum
we use kadane’s algo in a particular way
by first finding the normal max subarray sum
using kadane’s algo
storing in a a variable
inverting the elements of the array
using kadane’s algo again
and then subtracting the negative of this sum from cumulative sum of original array
in the array:
8 -8 9 -9 10 -11 12
the max circular subarray sum is 22( staring from 12 and ending at 10)
how does the logic and the algorithm used logically relate with each other

#2

Hello @S19APP-PP0097,

Algorithm:

  1. maximum sum possible in linear manner , use kadane’s algorithm to compute this (say max_linear)

  2. Find the maximum sum possible in circular manner:
    …First negate all the elements of the array. i.e. covert negative nos. to positive and vice-a-versa example: 1- to 1 and 5 to -5.
    …Now, apply kadane’s algorithm on this modified array and find maximum value which the minimum value for actual array(say min2).
    …At last, add this min2 to the sum of all the elements of the actual array (say max2).

  3. Compare max1 and max2.

  4. Print the maximum of both.

I would suggest you to dry run this algorithm on following testcase:
2
7
8 -8 9 -9 10 -11 12
5
-10 2 -1 5 6

Dry running the logic on these test cases will clear your concept.
It’s better to explore yourself.

If you would face any problem, let me know.
Hope, this would help.

#3

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.