please explain the question.
Question-
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 numbers and next line contains n space separated integers.
1
7
8 -8 9 -9 10 -11 12.
output-22
Hello @Manish-Sahani-1732882830153569,
You have to consider the array as circular though it is linear.
This means that you should not consider 12 as the last element.
You are suppose to check for the sum of element in circular fashion like:
12,8 =20
-11,12,8 =9
12,8,-8 =12
And so on…
In your case the maximum sum appears with the elements in circular fashion:
12,8,-8,9,-9,10 = 22
Hope, this would help.
Give a like, if you are satisfied.
please give me a hint how to write code for this question
It’s the same as maximum subarray sum.
You have to solve this question for in two parts:
Algorithm:
maximum sum possible in linear manner , use kadane’s algorithm to compute this (say max_linear)
Find the maximum sum possible in circular manner:
…First negate all the elements of the array. i.e. covert negative nos. to positive and vice-a-versa example: 1- to 1 and 5 to -5.
…Now, apply kadane’s algorithm on this modified array and find maximum value which the minimum value for actual array(say min2).
…At last, add this min2 to the sum of all the elements of the actual array (say max2).
Compare max1 and max2.
Print the maximum of both.
Hope, this would help.
Give a like if you are satisfied.