Maximum Circular Sum

#1

i am not getting the question . Pls explain it clearly and give some more examples

#2

Hello @i_am_dekard_shaw,

Hello @kunaldude04,

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.

Algorithm:
It’s the same as the maximum subarray sum.
You have to solve this question for in two parts:

  1. maximum sum possible in a linear manner, use kadane’s algorithm to compute this (say max_linear)

  2. Find the maximum sum possible in a 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 a 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).

  3. Compare max1 and max2.

  4. Print the maximum of both.

Hope, this would help.
Give a like if you are satisfied.

#3

i still dont understand why to invert the sign …whats the use? pls explain how it is working

#4

Hello @S18ML0016,

Negation is done to find the minimum sum for the original array which is the maximum sum of the negated array.
Thus, this maximum sum can be found using Kadane’s algorithm.
Then add this sum to the cumulative sum.
The result will be the maximum sum possible in a circular fashion which max2.

While max1 is the maximum sum possible in a linear manner.

We have to consider two cases while solving this problem:
Case 1: When the maximum sum SubArray is present in the normal order of an 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 a circular fashion.
Inversion of the array is required only to find the maximum sum in a circular fashion.
Example,
{10, -12, 11}
The max sum is 21 (11+10)
Inverted array, {-10,12,-11}
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:
Our array is like a ring and we have to eliminate the maximum continuous negative (i.e. the minimum sum) that implies maximum continuous positive Sum(i.e. maximum sum) in the inverted arrays.

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

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

Then, we will add the maximum sum of the inverted array to the Sum all the elements of the original array(i.e. cumulative sum).

At last, compare the max sum obtain from both the cases and print the larger one.

Hope, this would help.
Give a like if you are satisfied.

2 Likes
#5

@S18ML0016 thanks …awesome explanation…