Maximum circular sum doubt

#1

its written “numbers are arranged in circular form” what does this mean
and then its said we have to find max sum of consecutive numbers ?
question isn’t clear
i am unable to understand the whole question explain plz

#2

Here, you have to considered the given array as a circular sequence.
example:
for the array : {-1,2,8,-5,6}
the sub-sequences are:
{-1}=-1
{-1,2} = 1(sum)
{-1,2,8} = 9
{-1,2,8,-5}= 4
{-1,2,8,-5,6} = 10
{2]=2
{2,8} = 10
{2,8,-5}=5
…
…
{6}=6
{6,-1}=5 (coz array is considered circular)
{6,-1,2} =7
…
Now, you have to print the sum, that is maximum amongst all the sum computed.

#3

can u explain me logic to solve this problem

#4

We have to consider two cases while solving this problem:
Case 1: When the maximum sum SubArray is present in the normal order of array.
Example,
{-10, 2, -1, 5}
Max sum is 5

{-2, 4, -1, 4, -1}
Max sum is 7 (4+(-1)+4)
Use Kadane’s algorithm

Case 2:When max sum subArray is Present in circular fashion.
Inversion of the array is required only to find the maximum sum in circular fashion.
Example,
{10, -12, 11}
The max sum is 21 (11+10)
Inverted array, {-10,12,-11} //change of sign
Maximum sum is 12
Cumulative sum of original array is 9
Max sum=9+12=21

{12, -5, 4, -8, 11}.
The max sum is 23 (11+12)
Inverted array, {-12,5,-4,8,-11}
Maximum sum is 9 (5+(-4)+8)
Cumulative sum of original array is 14
Max sum=14+9=23

Note:
Inversion is done to apply Kadane’s algorithm which finds the maximum sum.

Hence, the maximum sum of inverted array would be the minimum sum of the original array.

Then, we will add the maximum Sum of inverted array with the Sum of all the elements of the original array(i.e. cumulative sum).
Suppose, cumulative sum is S=s-a
and max sum of inverted array is a
Adding both S+a=s-a+a=s(required sum)

Steps:
1.Find sum using both cases

2.At last compare the max sum obtain from both the cases
3. print the larger one.

Kadane’s Algorithm:
1.Initialize:
max_so_far = 0
max_ending_here = 0

2.Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
© if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far

This will help.
If you still have doubts, feel free to ask

1 Like
#5

i need your help the above you explain is very heplfull to me to understand.
but when i running my code on dev c++ i am getting the correct ans but on ide im getting worng and pls help me out

here is my code https://ide.codingblocks.com/s/93724

#6

There is a problem in the logic that you have implemented.
I would suggest you to dry run your code on above mentioned test cases.

#7

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.