Can u help me understand the below q and solve this using cpp

#1

You are provided n numbers (both +ve and -ve). Numbers are arranged in a circular form. You need to find the maximum sum of consecutive numbers.
Input Format

First line contains integer t which is number of test case.
For each test case, it contains an integer n which is the size of array and next line contains n space separated integers denoting the elements of the array.
Constraints

1<=t<=100
1<=n<=1000
|Ai| <= 10000
Output Format

Print the maximum circular sum for each testcase in a new line.
Sample Input

1
7
8 -8 9 -9 10 -11 12

Sample Output

22

Explanation

Maximum Circular Sum = 22 (12 + 8 - 8 + 9 - 9 + 10)

#2

hello @Kash-Moulik-3715574511847721

r u aware of kadane algorithm ?

#3

yeah I am aware of kadane algo

#4

@Kash-Moulik-3715574511847721

then check this->
The maximum subarray sum in circular array is maximum of following

  • Maximum subarray sum in non circular array
  • Maximum subarray sum in circular array.

Example - [1,2,5,-2,-3,5]
Steps -

  • Find the maximum subarray sum using Kadane Algorithm. This is maximum sum for non circular array.

image
image890×300 25.4 KB

  • 1+2+5 = 8
  • For non circular sum,
    Step 1) find the minimum subarray sum of array.

image
image851×281 23.7 KB

-2-3 = -5
Step 2) Now find the total sum of array = 1 + 2 + 5 -2 - 3 + 5 = 8
Step 3) The max subarray sum for circular array = Total Sum - Minimum subarray Sum
= 8 - (-5) = 8 + 5 = 13
As illustrated above, substracting minimum subarray sum from total sum gives maximum circular subarray sum.
Answer = Max ( Non circular max sum + circular max sum ) = max(8,13) = 13

#5

cpp soln would be good too

#6

@Kash-Moulik-3715574511847721

#7

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.