Maximum Circular Sum

#1

i have tried this problem by applying two loops with kadane’s algorithm. Is my approach is right or not? need help.

#2

@samk86676 I don’t think so this will give the correct answer. The actual approach is as follows:
For maximum circular sub array sum you need to consider the maximum of these 2 cases:

  • The maxm sum subarray obtained in non circular fashion as in normal Kadane’s algorithm.Apply normal Kadane on the array and obtain this.
  • The maxm circular sub array sum is obtained in a circular fashion.

To compute the 2nd case:
As you know that Kadane algo gives the maxm subarry sum…so if you invert the sign of each element of the array and then apply Kadane, the maxm subarray sum now obtained will actually be the minimum subarray sum for the original array.
Consider array elements as: 1 2 -1 -3 4 6

  1. maximum subarray sum in non circular fashion is: 4+6=11
  2. on inverting the signs, the array becomes: -1 -2 1 3 -4 -6
    Now applying Kadane, maxm subarry sum is: 1+3=4
    So minimum subarray sum for the original array is: -4
  3. Now cumulative sum of the original array is: 1+2-1-3+4+6= 9
    If you subtract the minimum sub array sum from cumulative sum you get: 9-(-4)=13 which is actually the
    maximum subarray sum in circular fashion ie. 4+6+1+2=13 .
    So now the answer will be max(11,13)=13.

Hope this helps :slightly_smiling_face:

#3

Whether I need to consider one of the two cases you mentioned above or Maximum of these two?

#4

maxm of these two cases will give the answer

#5

Thank you so much…
How we can solve the problem if we want to find the answer in a circular fashion?

#6

I have explained the process. Try to implement on yourself…If you are unable to do then i will share the code with you.