Omkar and Circle
Contest: Codeforces Round 655 (Div. 2)
Difficulty rating: 2100
Tags: brute force, dp, games, greedy

Danny, the local Math Maniac, is fascinated by circles, Omkar's most recent creation. Help him solve this circle problem!

You are given $$$n$$$ nonnegative integers $$$a_1, a_2, \dots, a_n$$$ arranged in a circle, where $$$n$$$ must be odd (ie. $$$n-1$$$ is divisible by $$$2$$$). Formally, for all $$$i$$$ such that $$$2 \leq i \leq n$$$, the elements $$$a_{i - 1}$$$ and $$$a_i$$$ are considered to be adjacent, and $$$a_n$$$ and $$$a_1$$$ are also considered to be adjacent. In one operation, you pick a number on the circle, replace it with the sum of the two elements adjacent to it, and then delete the two adjacent elements from the circle. This is repeated until only one number remains in the circle, which we call the circular value.

Help Danny find the maximum possible circular value after some sequences of operations.

Input format:
The first line contains one odd integer $$$n$$$ ($$$1 \leq n < 2 \cdot 10^5$$$, $$$n$$$ is odd)  — the initial size of the circle.

The second line contains $$$n$$$ integers $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$0 \leq a_{i} \leq 10^9$$$)  — the initial numbers in the circle.

Output format:
Output the maximum possible circular value after applying some sequence of operations to the given circle.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case, here's how a circular value of $$$17$$$ is obtained:

Pick the number at index $$$3$$$. The sum of adjacent elements equals $$$17$$$. Delete $$$7$$$ and $$$10$$$ from the circle and replace $$$2$$$ with $$$17$$$.

Note that the answer may not fit in a $$$32$$$-bit integer.

Example input:
3
7 10 2

Example output:
17

Example input:
1
4

Example output:
4

Editorial:
First note that any possible circular value consists of the sum of some $$$(n+1)/2$$$ elements. Now let's think about how these $$$(n+1)/2$$$ values would look like in the circle.
Let's consider any one move on index $$$i$$$. $$$a_i$$$ will be replaced with the sum of $$$a_{i-1}$$$ and $$$a_{i+1}$$$ (wrap around to index $$$1$$$ or $$$n$$$ if needed). Then let's consider making a move on $$$i+2$$$, since it will be adjacent to $$$i$$$ after the first move. Then its value will become $$$a_{i-1}+a_{i+1}+a_{i+3}$$$. This implies that alternating values play a role in the construction of the $$$(n+1)/2$$$ values contained in the final circular value.
Now let's consider the final move when there's $$$3$$$ elements left in the circle. This is the only move that takes the sum of two adjacent elements in the initial circle. With this observation, we can achieve our final construction as follows:
Choose any $$$(n+1)/2$$$ elements in the initial circle such that exactly one pair of chosen numbers are adjacent to each other. The answer will be the maximum of the circular value over all possible constructions.
While there are ways involving complicated prefix sums/segment trees, the cleanest implementation is as follows: create an array whose values consists of $$$[a_1, a_3, ..., a_n, a_2, a_4, ..., a_{n-1}]$$$. Append this new array to itself to account for the circular structure. Now all you simply have to do is to find the maximum sum over all subarrays of length $$$(n+1)/2$$$. This can be done with sliding window in $$$O(n)$$$ time.