Click here to Skip to main content
15,902,840 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
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
Posted
Updated 17-Dec-22 20:07pm
Comments
Patrice T 18-Dec-22 6:13am    
And you have a question ?

1 solution

While we are more than willing to help those that are stuck, that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

But ask yourself this: why do you read the values in one loop, then run through them again in another? And, if all you are looking for is the largest pair of numbers why would you need the third loop at all?
Think about the problem carefully, and it's pretty obvious that you don't need to actually move any values ...

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900