Given a circular array of N integers (i.e. A[0] and A[N — 1] are adjacent to each other), what's the maximum number of adjacent pairs that you can form whose sum are even? Note that each element can belong to at most one pair.

This is a recent problem that I encountered, but my approach is wrong. I know that the sum of two numbers of the same parity produce an even sum (so odd and odd, or even and even), but the whole "wrap-around" part is what's getting me. In particular, I can't figure out whether or not it's optimal to pair a value with its left neighbor or its right neighbor. The current algorithm I'm thinking of is as follows:

• For each index 0 <= i <= n — 1, try to pair A[i] with A[i + 1] by checking their parity.

• If both A[0] and A[n — 1] are unpaired at the end, pair them if they have the same parity.

This is a wrong algorithm since it fails for [1, 1, 1, 0, 1] in which case it's optimal to pair A[0] with A[n — 1] and A[1] with A[2]. Does anyone have any suggestions?

Thanks.