Maximum Circular sum -

#1

Sir , Can you please tell how to approach this question? I am not able to see how to solve it.

#2

@amartya970914
In this problem, there can be two cases i.e. either the subarray having maximum sum is

obtained in a circular fashion or the subarray having maximum sum is obtained in a non-
circular fashion.

The non-circular maximum sum subarray can be obtained directly by Kadane’s Algorithm.
But the subarray with circular fashion cannot be solved by Kadane’s algorithm.
So to solve this problem we will first calculate the maximum sum subarray using Kadane’s
Algorithm and store it in a variable, say candidate1. Then we will invert the sign of every
element of the array and again apply Kadane’s Algorithm to calculate the maximum sum
subarray of this new inverted array.
But we should keep in mind the fact that the maximum sum of the inverted subarray is actually
the minimum sum subarray for the original array. So if we subtract the negative value of this
new sum from the cumulative sum of the original array we will get another candidate for the
answer and name it candidate2. Then compare both the candidates and return the larger
number.
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 Likes
#3

sir, i studied about the approach of this problem, but i want to know that when during any real-time competition, how will i get to know the best optimised solution of the problem.

#4

@amartya970914 did you implement your approach eariler ?
this is simple application of kadane algorithm you have to think using kadane algorithm in competition also

1 Like
#5

thanks bruh…, lovely explanation , keep helping the way u helped…

1 Like
#6

Hey Amartya,
As you are not responding to this thread, I am marking your doubt as Resolved for now. Re-open it if required.

Please mark your doubts as resolved in your course’s “ Ask Doubt ” section, when your doubt is resolved.

#7

#include
using namespace std;
int kadane_algo(int arr[],int test)
{
int ms=0,cs=0;
for(int j=0;j<test;j++)
{
cin>>arr[j];
}
for(int j=0;j<test;j++)
{
cs=cs+arr[j];
if(cs<0){
cs=0;
}
ms=max(cs,ms);
}
return ms;
}
int maxCircularSum(int a[], int n)
{

int max_kadane = kadane_algo(a, n);
int max_wrap = 0, i;
for (i=0; i<n; i++)
{
max_wrap += a[i];
a[i] = -a[i];
}
max_wrap = max_wrap + kadane_algo(a, n);
int y = (max_wrap > max_kadane)? max_wrap: max_kadane;
cout<<y;
}
int main()
{
int n;
cin>>n;
int test[n];
for(int i=0;i<n;i++)
{
cin>>test[i];
int arr[test[i]];
int x = maxCircularSum(arr,test[i]);
//cout<<x;
}
return 0;
}

#8

glat kyun aa rha , answer being generated is 22 , but on submitting the code , it says wrong answer.

#10

Dear Ajeet Shankar ,
I studied your code .Well written . The error was entering array elements everytime you called the kadane algo function which was not required the second time the function was called .
I have made changes in your code and it passed the test cases successfuly .I have marked where the changes were made .You can contact me at [email protected] .
https://ide.codingblocks.com/s/103916

#11

why are we inverting element after adding we should have done first in circular sum funcn

#12

5
-1 -4 -5 -2 -1
your code is failed for this T.S

#13

but why do we inverted the array and then also take negative of every element

#14

#include
using namespace std;

int kadenalgo(int a[],int n){
int cs=a[0]; //current sum as first element (to deal with all -ve i/p)
int ms=a[0]; //max sum as first element (to deal with all -ve i/p)

	for(int i=1;i<n;i++) // start loop from 1 
	{
      // check if curr sum <= 0 reinitialise it to 0 
		if(cs<0)
		{
			cs = 0;
		}
        cs = cs + a[i];
		
		ms = max(cs,ms);
	}
	return ms;
}

int main() {
int t,cumsum=0; //no of testcases
cin>>t;

for(int i=0;i<t;i++)
{	
	int n; //move it inside the test case
	cin >> n;
	int a[10000];  // always take this to be n
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		cumsum=cumsum+a[i];
	}
int can1=kadenalgo(a,n);
for(i=0;i<n;i++)
{a[i]=-1*a[i];
}
int sum=kadenalgo(a,n);
int can2=cumsum+sum;
cout<<max(can1,can2);

}
return 0;
}

i am getting correct output but still test cases are failing

#15

you have given the code of hello world not of the circular sum.