663. Maximum Sum in a Circular Array
0
Medium
Given a circular array of integers called nums with a length of n, find the maximum possible sum of a non-empty subarray within nums.
A circular array means that the last element of nums is connected to the first element. In other words, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].
Input Format
The first line of the input contains an integer t, which represents the number of test cases. Each test case is described by two lines. The first line contains an integer n, which is the size of the array nums. The second line contains n space-separated integers, representing the elements of nums.
Output Format
For each test case, print the maximum circular sum on a new line.
Example
Input
1
7
8 -8 9 -9 10 -11 12
Output
22
Constraints
1<=t<=100
1<=n<=1000
|Ai| <= 10000
1<=n<=1000
|Ai| <= 10000
Loading...
View Submissions
Console