Maximum Circular Sum

#1


Please, help me where i was wrong.

#2

Hello @Gade_Deepthi,

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
…
print the maximum.

First, create a program with nested loop, with complexity O(N)
this would help you understand the approach.
then, try to reduce the complexity to O(N)

You have to use kadane’s algorithm to solve this:

  1. 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).
  2. Compare max1 and max2.
  3. Print the maximum of both.

If you still face problem, feel free to ask.
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.