시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 | 512 MB | 64 | 28 | 21 | 46.667% |
According to our long-established tradition, the best statements are those kept short.
Given a sequence of integers, find the largest sum of a consecutive subsequence of odd length.
The first line of input contains the number of test cases $z$. The descriptions of the test cases follow.
The first line of each test case contains the length of the sequence $n$ ($1 \leq n \leq 1\,000\,000$).
The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$), the elements of the sequence.
The total length of all sequences in all test cases does not exceed $5\,000\,000$.
For each test case, output the largest sum on a separate line.
1 4 8 -7 9 1
10