Problem 3
Time limit: 1.0s
Memory limit: 256M
Author:
root
Allowed languages
C
Problem Description
You and your friend were sitting on the first and last bench respectively during the quiz. Recently, you got hold of an array that consists of the marks of all N
students seated for the quiz (from the first seat to the last seat in the same order). You want to maximize the sum of marks you and your friend get by potentially modifying the array. However, you don't want to raise suspicion. So, you both decide to perform a single operation on the array of the form:
Cyclically shifting the array to the right by any amount
Here, a right cyclic shift by one unit on the array A={A1,A2,A3,A4}
would transform the array unto A={A4,A1,A2,A3}. Similarly, a right cyclic shift by some k units is equivalent to shifting it by one unit for k
times.
Note that after a cyclic shift, the scores of you and your friend are still given by the values present at the first and last place of the array respectively. Only the values in those places may be different from the original array due to the shift operation.
By right cyclic shifting the array by any amount at most once, find the maximum sum of marks you and your friend can achieve.
Input Format
The first line of input contains a single integer denoting the number of test-cases T. Then, 2T
lines follow:
For each test-case:
The first line contains a single integer N
that denotes the size of the array A
.
The second line contains N
space-separated integers A1,A2,....,AN describing the array A
that holds the marks of all the students.
Input constraints
1≤T≤105
2≤N≤105
0≤Ai≤109
It is guaranteed that the sum of N
across all test-cases does not exceed 105
.
Output Format
For each test-case: output on a single line the maximum sum of marks you and your friend can get by right cyclically shifting the array by any amount at most once.
Sample Input
Copy
2
4
1 2 3 3
2
1 2
Sample Output
Copy
6
3
Note
Explanation for sample input 1:
For the first test-case of the first sample: notice that by right shifting array cyclically by 1 unit, you obtain the array A={3,1,2,3}
, where you and your friend both have 3 marks.
We can show that the sum 3+3=6
is the maximum sum possible.
For the second test-case of the first sample: the sum is already maximized and hence the array doesn't require any cyclic shifts.
#include <stdio.h>
int
main ()
{
int t;
scanf ("%d", &t);
int arr[t], sum[t + 1];
while (t--)
{
for (int i = 0; i < t; i++)
{
scanf ("%d", &arr[i]);
}
for (int j = 0; j < t - 1; j++)
{
sum[j] = arr[j] + arr[j + 1];
}
sum[t - 1] = arr[t - 1] + arr[0];
sum[t] = 0;
for (int k = 0; k < t ; k++)
{
if (sum[t] < sum[k])
{
sum[t] = sum[k];
}
}
printf ("%d", sum[t]);
}
return 0;
}
What I have tried:
Here, a right cyclic shift by one unit on the array A={A1,A2,A3,A4}
would transform the array unto A={A4,A1,A2,A3}. Similarly, a right cyclic shift by some k units is equivalent to shifting it by one unit for k
times.
Note that after a cyclic shift, the scores of you and your friend are still given by the values present at the first and last place of the array respectively. Only the values in those places may be different from the original array due to the shift operation.
By right cyclic shifting the array by any amount at most once, find the maximum sum of marks you and your friend can achieve.
Input Format
The first line of input contains a single integer denoting the number of test-cases T. Then, 2T
lines follow:
For each test-case:
The first line contains a single integer N
that denotes the size of the array A
.
The second line contains N
space-separated integers A1,A2,....,AN describing the array A
that holds the marks of all the students.
Input constraints