Maximum circular sum problem. What is the approach ?
How to solve this problem(Maximum circular sum)
approach is using kadan’s algorithm for circular subarray
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 contributing, invert sign of each element and then run Kadane’s algorithm.
now take max of these two case
Sir what is the meaning of “wrapping”?
wrapping means folding the array
kind of circular array
Ok sir thanks for explaining 