Maximum Circular Sum Array Problem

#1
  1. In my solution , I’ve considered only the part where there is wrapping , i.e., I have calculated the total sum of array and then inverted it’s sign , calculated negative max subarray and subtracted. It passed all the test cases.
  2. But in editorial solution, it is written that we have to apply kadane’s algo on whole array and the part I have done in point 1 and compare the output of the two which is max, and return the answer.
  3. Is Kadane’s step necessary? Won’t the part circular part(said in 1) be effective alone?
#2

Here is my solution :#include using namespace std; int kadane(int arr[], int n){ int start = 0; int end = 0; int max_sum = 0; int sum = 0; while(end< n){ if(sum > 0){ sum = sum + arr[end]; }else{ sum = arr[end]; } if(sum > max_sum){ max_sum = sum; } end++; } return max_sum; } void circularsum(){ int t; cin >> t; while(t–>0){ int n; cin>>n; int arr[n];int sum =0; for(int i =0; i<n; i++){ cin>>arr[i]; sum += arr[i]; arr[i]=-arr[i]; } int neg_max = kadane(arr,n); cout << sum+neg_max<<endl; } } int main() { circularsum(); return 0; }

#3

You are also using kadane’s algo

#4

So, is my solution overall correct?

#5

But it’s a better way
we have to apply kadane’s algo on whole array and the part I have done in point 1 and compare the output of the two which is max, and return the answer.

#6

@ap8730390
always Not correct

#7

Please tell me the cases where it will be incorrect

#8

I mean the case where kadane’s output will be greater than inverting the sign part

#9

result = kadens(arr); // origal Array
long sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
arr[i] = -arr[i];
}
sum = sum + kadens(arr);
System.out.println(Math.max(result, sum));// Your test case will fail. When sum <result

	}
#10

@ap8730390
you got it??

#11

I am aware of that , but I was unable to find any test case where the result < sum

#12

Sorry , sum < result

#13

Like it can happen in the case when there is no overlapping only?

#14

1
39
-175 188 -126 33 -43 481 293 158 70 499 217 639 369 163 422 594 -27 647 231 262 482 190 92 591 -143 -85 321 -43 374 291 747 751 31 -179 337 540 -146 -170 -102

#15

Its Correct output is:
9367
And Your Code’s output is:
9192

#16

Got it! Thankyou So Much

#17

please rate your experience here