Circular One-Pair Maximum Sum

You are given an integer array nums arranged in a circle: positions i and i+1 are adjacent, and so are the first and last positions.

Choose a subset of positions such that at most one pair of adjacent positions is chosen across the entire selection. (In particular, three consecutive chosen positions are impossible, since that would contain two adjacent pairs.) For nums.length = 2 the two positions count as a single adjacency.

Return the maximum possible sum of the chosen values.

Examples

Example 1

Input: nums = [9, 8, 1, 2]
Output: 17
Explanation: Choose positions 0 and 1 (9 + 8). They are adjacent, and that is the
one allowed pair. No larger selection is valid.

Example 2

Input: nums = [5, 4, 3]
Output: 9
Explanation: In a circle of three, every two positions are adjacent. Choosing
5 and 4 uses the single allowed pair. All three would form three adjacent
pairs, which is not allowed.

Example 3

Input: nums = [6, 7, 1, 2, 8, 3]
Output: 21
Explanation: Choose positions 0, 1 and 4 (6 + 7 + 8). Positions 0 and 1 are
the one allowed adjacent pair, and position 4 touches neither of them. Adding
position 5 (value 3) is not allowed: it is adjacent to both position 4 and,
around the circle, position 0.

Example 4

Input: nums = [8, 2, 3, 9, 1, 4]
Output: 21
Explanation: Choose positions 0, 3 and 5 (8 + 9 + 4). Positions 5 and 0 are
adjacent around the circle, so they form the one allowed pair.