You are given an array A = [A_{1}, A_{2}, \ldots, A_{N}] of length N.

You can right rotate it any number of times (possibly, zero). What is the maximum value of A_{1} + A_{N} you can get?

Note: Right rotating the array [A_{1}, A_{2}, \ldots, A_{N}] once gives the array [A_{N}, A_{1}, A_{2}, \ldots, A_{N-1}]. For example, right rotating [1, 2, 3] once gives [3, 1, 2], and right rotating it again gives [2, 3, 1].

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases. The description of the test cases follows.
- The first line of each test case contains a single integer N, denoting the length of array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} — denoting the array A.

------ Output Format ------ 

For each test case, output on a new line the maximum value of A_{1}+A_{N} you can get after several right rotations.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ across all test cases does not exceed $10^{5}$

----- Sample Input 1 ------ 
3
2
5 8
3
5 10 15
4
4 4 4 4

----- Sample Output 1 ------ 
13
25
8

----- explanation 1 ------ 
Test case $1$: Whether you right rotate the array or not, you will always end up with $A_{1}+A_{N} = 13$.

Test case $2$: It is optimal to right rotate the array once after which the array becomes $[15,5,10]$ with $A_{1} + A_{N} = 25$.

Test case $3$: No matter how much you right rotate the array, you will always obtain $A_{1} + A_{N} = 8$.

Source: codechef | Difficulty: EASY
Tags: Implementation

Greedy algorithms


Solutions:
T = int(input())
for i in range(T):
	max = 0
	n = int(input())
	a = list(map(int, input().split()))
	m = n - 1
	x = a[0] + a[m]
	for j in range(m):
		y = a[m] + a[m - 1]
		if y > max:
			max = y
		m = m - 1
	if x > max:
		max = x
	print(max)


t = int(input())
for i in range(t):
	max_num = 0
	n = int(input())
	a = list(map(int, input().split()))
	m = n - 1
	x = a[0] + a[m]
	for j in range(m):
		y = a[m] + a[m - 1]
		if y > max_num:
			max_num = y
		m -= 1
	if x > max_num:
		max_num = x
	print(max_num)


T = int(input())
for i in range(T):
	max_num = 0
	size = int(input())
	lst = list(map(int, input().split()))
	i = len(lst) - 1
	loc = lst[0] + lst[i]
	for x in range(i):
		num = lst[i] + lst[i - 1]
		if num > max_num:
			max_num = num
		i -= 1
	if max_num < loc:
		max_num = loc
	print(max_num)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	m = 0
	for i in range(N):
		m = m if m > A[i] + A[i - 1] else A[i] + A[i - 1]
	print(m)


n = int(input())
for i in range(n):
	x = int(input())
	l = list(map(int, input().split()))
	a = 0
	a1 = 0
	for i in range(x):
		a = l[i] + l[i - 1]
		if a > a1:
			a1 = a
	print(a1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = a[0] + a[-1]
	for i in range(1, n):
		s = max(s, a[i] + a[i - 1])
	print(s)


for i in range(int(input())):
	x = int(input())
	ar = list(map(int, input().split()))[:x]
	s1 = 0
	s = 0
	for i in range(len(ar)):
		s1 = ar[i] + ar[i - 1]
		if s1 > s:
			s = s1
	print(s)


t = int(input())
for j in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in range(n):
		c = c if c > l[i] + l[i - 1] else l[i] + l[i - 1]
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = l[0] + l[n - 1]
	for i in range(0, n - 1):
		if l[i] + l[i + 1] > m:
			m = l[i] + l[i + 1]
	print(m)


for testcases in range(int(input())):
	arr = int(input())
	n = list(map(int, input().split()))[:arr]
	temp = n[0] + n[-1]
	for val in range(arr - 1):
		if temp < n[val] + n[val + 1]:
			temp = n[val] + n[val + 1]
	print(temp)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	Sum = A[0] + A[-1]
	for i in range(N - 1):
		Sum = max(Sum, A[i] + A[i + 1])
	print(Sum)


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	s = int(a[0]) + int(a[-1])
	for i in range(len(a) - 1):
		c = int(a[i]) + int(a[i + 1])
		s = max(c, s)
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	mx = 0
	for i in range(n - 1, 0, -1):
		if A[i] + A[i - 1] > mx:
			mx = A[i] + A[i - 1]
	if A[0] + A[n - 1] > mx:
		print(A[0] + A[n - 1])
	else:
		print(mx)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = []
	for i in range(n):
		x = l[i % n] + l[(i + 1) % n]
		a.append(x)
	print(max(a))


for j in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	max = 0
	for i in range(n):
		s = a[i - 1] + a[i]
		if s > max:
			max = s
	print(max)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	z = a[0] + a[-1]
	for i in range(n - 1):
		y = a[i] + a[i + 1]
		if z < y:
			z = y
	print(z)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	m = 0
	for i in range(len(a)):
		if m > a[i] + a[i - 1]:
			m = m
		else:
			m = a[i] + a[i - 1]
	print(m)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	sum = arr[0] + arr[-1]
	for i in range(n - 1):
		sum = max(sum, arr[i] + arr[i + 1])
	print(sum)


t = int(input())
for i in range(t):
	n = int(input())
	m = 0
	p = list(map(int, input().split()))
	for j in range(n):
		if m > p[j] + p[j - 1]:
			m = m
		else:
			m = p[j] + p[j - 1]
	print(m)


def max_value(arr, n):
	if n == 0:
		return -1
	elif n == 1:
		return arr[0]
	elif n == 2:
		return arr[0] + arr[1]
	else:
		max_sum = 0
		for i in range(n):
			sum = arr[(n + i) % n] + arr[(n - 1 + i) % n]
			if max_sum < sum:
				max_sum = sum
		return max_sum
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	print(max_value(arr, n))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = 0
	for i in range(n):
		m = m if m > l[i] + l[i - 1] else l[i] + l[i - 1]
	print(m)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	max_sum = A[0] + A[-1]
	for i in range(N - 1):
		max_sum = max(max_sum, A[i] + A[i + 1])
	print(max_sum)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	j = b[0] + b[a - 1]
	for i in range(0, a - 1):
		j = max(j, b[i] + b[i + 1])
	print(j)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	maxi = 0
	for i in range(n):
		if maxi < l[0] + l[-1]:
			maxi = l[0] + l[-1]
		l.insert(0, l[n - 1])
		l.pop(-1)
	print(maxi)


t = int(input())
for i in range(t):
	a = int(input())
	b = [int(b) for b in input().split()]
	c = 0
	d = []
	for i in range(len(b)):
		c = b[i] + b[i - 1]
		d.append(c)
	print(max(d))


for i in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	maxsum = 0
	for i in range(n):
		maxsum = max(maxsum, lis[i] + lis[i - 1])
	print(maxsum)


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	m = 0
	for i in range(n):
		m = max(m, l[i] + l[i - 1])
	print(m)
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	m = arr[0] + arr[n - 1]
	for i in range(n - 1):
		m = max(m, arr[i] + arr[i + 1])
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	ls = list(map(int, input().split()))
	mx = 0
	for i in range(n):
		mx = max(mx, ls[i] + ls[i - 1])
	print(mx)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = a[0] + a[-1]
	for i in range(n - 1):
		if m < a[i] + a[i + 1]:
			m = a[i] + a[i + 1]
	print(m)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = a[0] + a[n - 1]
	for i in range(n - 1):
		if a[i] + a[i + 1] > s:
			s = a[i] + a[i + 1]
	print(s)


for i in range(int(input())):
	curr = 0
	n = int(input())
	nums = list(map(int, input().split()))
	for j in range(n):
		if curr > nums[j] + nums[j - 1]:
			curr = curr
		else:
			curr = nums[j] + nums[j - 1]
	print(curr)


for i in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in range(x):
		c = c if c > l[i] + l[i - 1] else l[i] + l[i - 1]
	print(c)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = l[0] + l[n - 1]
	for i in range(n - 1):
		if l[i] + l[i + 1] > s:
			s = l[i] + l[i + 1]
	print(s)


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	m = 0
	for i in range(x - 1):
		t = max(l[i - 1] + l[i], l[i] + l[i + 1])
		m = max(t, m)
	print(m)


n = int(input())
for i in range(n):
	x = int(input())
	arr = list(map(int, input().split()))
	c = 0
	for i in range(len(arr)):
		c = c if c > arr[i] + arr[i - 1] else arr[i] + arr[i - 1]
	print(c)


try:
	t = int(input())
	for r in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		ans = a[0] + a[-1]
		for i in range(1, n):
			k = a[i] + a[i - 1]
			if k > ans:
				ans = k
		print(ans)
except:
	pass


for _ in range(int(input())):
	x = int(input())
	a = list(map(int, input().split()))
	b = []
	for i in range(len(a) - 1):
		if i != len(a) - 1:
			b.append(a[i] + a[i + 1])
	b.append(a[0] + a[-1])
	print(max(b))


t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	s1 = 0
	s2 = 0
	for j in range(len(b)):
		s1 = b[j] + b[j - 1]
		if s1 > s2:
			s2 = s1
	print(s2)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	S = a[0] + a[-1]
	for i in range(n - 1):
		S = max(S, a[i] + a[i + 1])
	print(S)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	maxim = a[0] + a[-1]
	for i in range(n):
		x = a.pop(-1)
		a.insert(0, x)
		elem = a[0] + a[-1]
		if elem > maxim:
			maxim = elem
	print(maxim)


n = int(input())
while n > 0:
	len = int(input())
	lis = list(map(int, input().split()))
	al = []
	for i in range(len):
		t = lis.pop()
		lis.insert(0, t)
		ans = lis[0] + lis[-1]
		al.append(ans)
	print(max(al))
	n -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = []
	x.append(l[0] + l[n - 1])
	for i in range(n - 1):
		x.append(l[i] + l[i + 1])
	print(max(x))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		c = c if c > a[i] + a[i - 1] else a[i] + a[i - 1]
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	sm = l[0] + l[n - 1]
	for i in range(n - 1):
		if sm < l[i] + l[i + 1]:
			sm = l[i] + l[i + 1]
	print(sm)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = l[0] + l[-1]
	for z in range(n):
		temp = l[-1]
		l.pop(n - 1)
		l.insert(0, temp)
		if l[0] + l[-1] > s:
			s = l[0] + l[-1]
	print(s)


for i in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	s = l[0] + l[-1]
	for i in range(N - 1):
		s = max(s, l[i] + l[i + 1])
	print(s)


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	gorb = a[0] + a[-1]
	for i in range(0, n - 1):
		if a[i] + a[i + 1] > gorb:
			gorb = a[i] + a[i + 1]
	print(gorb)


for _ in range(int(input())):
	length = int(input())
	table = list(map(int, input().split()))
	value = 0
	maxvalue = 0
	for i in range(length):
		value = table[0] + table[-1]
		if value > maxvalue:
			maxvalue = value
		table.append(table[0])
		table.pop(0)
	print(maxvalue)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	max = a[0] + a[n - 1]
	i = 0
	while i <= n - 2:
		if a[n - 1 - i] + a[n - 2 - i] > max:
			max = a[n - 1 - i] + a[n - 2 - i]
		i += 1
	print(max)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	ans = array[0] + array[n - 1]
	for i in range(0, n - 1):
		if array[i] + array[i + 1] > ans:
			ans = array[i] + array[i + 1]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = 0
	for i in range(n - 1):
		if a[i] + a[i + 1] > b:
			b = a[i] + a[i + 1]
	print(max(b, a[0] + a[-1]))