Maximum circular sum

#1

in this problem i am applying kadane’s algorithm nut i didnot get the required output please point out my error

#2

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. Let us see how. Wrapping of contributing elements implies non wrapping of non contributing elements, so 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.

#3

maam actually i am unable to think when and why wrapping is required please explain the examples of both cases

#4

Let us take an example and dry run our code.
For an array, say 10, -3, -4, 7, 6, 5, -4, -1
Cumulative Sum of the original array is 16
candidate1 using Kadane’s algorithm on this array is 21 i.e from index 0 to 5
Now inverting this array it becomes -10, 3, 4, -7, -6, -5, 4, 1
Now applying Kadane’s algorithm on this new array we get the sum as 7 i.e from index 1 to 2.
So candidate2 will be cumulative_sum - (-7) i.e 16+7 which is 23
So candidate2 is greater than candidate1 so answer is 23
Here we can conclude that this algorithm works because it explains the fact the array’s sum
could have been maximum if the minimum sum elements sum were not present so we should exclude it.

#5

Maam what is wrapping ? Please explain i am unable to understand

#6


try to go through this then