Where it is going wrong ( maximum circular sum)

#1

#include
using namespace std;
int main()
{
int test,n,i,j,k,m;
cin>>test;
for(j=0;j<test;j++)
{
cin>>n;
int a[2n];
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
a[i+n]=a[i];
int cs=0,ms=a[0];
for(k=0;k<2n ;k++)
{
cs=cs+a[k];
ms=max(cs,ms);
if(cs<0)
cs=0;
else if(cs<=0)
i=k+1;
else if(2*n-k<=n-i)
break;
}
cout<<ms<<endl;
}
return 0;
}

#2

@anujsharmabadboy Hey in this code first make sure you update ms only after checking cs<0 or not, second.
Also the checking you are doing that whether you have reached the same index after moving out of n, should be done when we are updating max also.
If this resolves your doubt mark it as resolved.

#3

if i update ms only after checking cs<0 or not then if largest sum is -ve then it will zero to ms

aur ye m run kraa rha hu har input pe sahi answer de rha h

#4

@rishabhmahajan546 now please help me

#5

@rishabhmahajan546

bhai iissi question m doubt h answer run krane pe toh sahi de rha h lekin submit nhi ho rha code

#6

@anujsharmabadboy
This Question can be done using the brute force viz, by using two nested loops and checking the sum of every possible subset but this approach is in O(n^2). So, Now we are going to discuss an approach which solves the given problem in O(n).

Approach :
For finding the Maximum Contiguous sum we are using the kadane’s algorithm. But in the question the array is circular that means the maximum sum can be of elements which are a part of the wrapping or not. So,
There can be two cases for the maximum sum:
Case 1: The elements that contribute to the maximum sum are arranged such that no wrapping is there. Examples: {-10, 2, -1, 5}, {-2, 4, -1, 4, -1}. In this case, Kadane’s algorithm will produce the result.

Case 2: The elements which contribute to the maximum sum are arranged such that wrapping is there. Examples: {10, -12, 11}, {12, -5, 4, -8, 11}. In this case, we change wrapping to non-wrapping. Let us see how. Wrapping of contributing elements implies non wrapping of non contributing elements, so find out the sum of non contributing elements and subtract this sum from the total sum. To find out the sum of non contributing, invert sign of each element and then run Kadane’s algorithm. Our array is like a ring and we have to eliminate the maximum continuous negative that implies maximum continuous positive in the inverted arrays.
For implementation refer https://ide.codingblocks.com/s/236581

#7

Your code logic is incorrect try this test:
1
4
1 2 3 4

#8

@mayankA47
bhai wrapping aur non wrapping kya hota h
aur ye example bhi samajh nhi aaya
yeh sab toh geeks for geeks pe bhi nhi samajh aaya tha

#9

wrapping means maximum subarray includes a[0] after a[n-1](circular fashion). Now think this way:

  1. either the maximum subarray does not require wrapping, then considering it as normal array will give the answer using kadane’s algo.
  2. if wrapping is required, then think that sub-array which is not the part of answer is linear!, sum of this subarray can be found by inverting sign of every a[i], and then using kadane’s algorithm!