All Tracks Problem

Chocolate Day
Tag(s):

Medium

Problem
Editorial
Analytics

It’s 9th of February, Chocolate Day of valentine week!!!

Pařømîtå has “acute weakness” for chocolates. Now, as it is Valentine Week, so everyone in the CSE dept is tensed about getting a valentine by 14th. As Pařømîtå’s love for chocolates is well known to everyone, all the N boys of CSE dept have thought of impressing her by giving a huge number of chocolates to her on Chocolate Day.

Each of the N boys seated in a row have decided to give Ci number of chocolates. Now Pařømîtå sees a great opportunity to have large number of chocolates just for her. So she has decided to try to have maximum number of chocolates. But, again, if she takes chocolates from two adjacent seated boys, they would be feeling heartbroken. So, she doesn’t want to hurt anybody’s feelings. She falls in a dilemma thinking about how many maximum chocolates she can get in this given situation.

So she has approached you to solve this dilemma and help her know the maximum number of chocolates she can get.


INPUT
The input will start with a single integer T, denoting the number of test cases. Each test case will consist of two lines. First line will have a single integer N, denoting number of boys offering chocolates. Next line will contain N integers Ci separated by a single space, each denoting the number of chocolates offered by ith boy.

OUTPUT
For each test case, output a single integer denoting the maximum number of chocolates in a new line.

CONSTRAINTS

  • 1<=T<=1000
  • 1<=N<=50000
  • 0<=Ci<=105
SAMPLE INPUT
1
5
1 3 7 8 12
SAMPLE OUTPUT
20
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Jalpaiguri Government Engineering College

Challenge Name

Code Chronicles Season 3

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?