Test 0 is not passing

#1

// to find the maximum subarray considering the array is circular

//to solve this
// 1 find the total sum of the array
// 2 to find the minimum sum subarray
// 3 subtract the sum of the subarray from total array

#include
#include

using namespace std;

int maxCircularSub(int a[], int n)
{

int arrSum = 0;
int currentSum = 0;
int minSum = INT_MAX;

for (int i = 0; i < n; i++)
{
    arrSum += a[i];
}

for (int i = 0; i < n; i++)
{
    currentSum = currentSum + a[i];

    if (currentSum > 0)
    {
        currentSum = 0;
    }
    minSum = min(currentSum, minSum);
}
int maxCircularSum = arrSum - minSum;
return maxCircularSum;

}

int main()
{

int t;

cin>>t;

while(t>0)
{
        int n;

cin >> n;
int a[n];

for (int i = 0; i < n; i++)
{
    cin >> a[i];
}

cout << maxCircularSub(a, n)<<endl;

t--;
}

return 0;
}

#2

Hello @anandsingh3210 i have checked your code it is correct and producing correct answer for the test cases as well.

#3

sir, but my test case is not passing

#4

@anandsingh3210 your approach is not correct i got the error.
1
7
10 -3 -4 7 6 5 -4 -1
check for this test case : the output should be 23.
from these numbers: 7 + 6 + 5 - 4 -1 + 10

#5

try to think this way:
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.
if you have any doubt you can ask here:

#6

Sir the input u r trying to take is wrong as you inputting 7 elements in an array but you are ginving 8 inputs in array i.e 10 -3 -4 7 6 5 -4 -1

#7

@anandsingh3210 oops sorry my bad.
but what is the approach you are using?
see for this test case:
1
9
-3 -18 -22 -21 -17 16 -14 28 -22
your code is not producing the correct ouput
correct output should be: 30 which is from: 16 -14 28

#8

try to implement in the way i have mentioned above:

#9

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.

#10

hello @anandsingh3210
u have reopend the doubt.
pls let me know what issue u r facing now

#11

what I was earlier doing was finding the total array Sum then applying kadane’s algo in modified form to find min subarray then subtracting from the total sum. At that time only 1 test case was not passing and now also no idea what to do?

I also tried to reverse the sign of array and applied standard kadane then adding to total array sum now everything failed.

#12

u are considering only one case (i.e where u have to subtract a subarray from given array).

u missed case 2. i.e apply simple kadane without any modifications on given array.

check this for clarity->

#13

ok
1st
consider 2 cases - 1circular, 2 straight

2nd find maxSub for strainght
3rd find for straight
4th compare both and return max
am I correct ?

#14

yeah correct . . . . .

1 Like
#15

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.