Gagan's Reward (Medium)

4

1 votes
Easy-Medium
Problem

Gagan's teacher provide him rewards daily but he is a very lazy person so he doesn't want to go college daily, but he also wants to maximize his rewards without going to college daily. Now your work is to tell Gagan how much maximum reward he will get at the end.

Constraints
1<=t<=100
1<=N<=10^5
1<=A[i]<=10^9

Input :
First line contain a single integer 't' No. of test cases
next 't' line contains a integer 'N' no. of days
next line contains 'N'space seperated integers denoting the value of reward at ith day

Output:
print a single integer 'M' that denotes maximum reward.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In The First test case rewards given 1 2 3 As mentioned in the questoin Gagan doesn't want to attend classes daily,and want maximum reward. So, in order to do that either he can go on first day and last or just second day. if he'll only go on second day he'll get 2 rewards ,but in other case he can get 4 so maximum is 4.

Editor Image

?