The first necessary observation, which is that for each block (adjacent even odd index in array), [0,1],[2,3],[4,5], etc. The way to get the maximum sum is always pair a number in range [1,2*N] with a number in range[N + 1, 2*N].

There is a useful observation, split the numbers from 1 to 2 * N, and label from 1 to N as lower and N + 1 to 2 * N as upper. It is guaranteed that the lower and upper will be those for each block of size 2. And then you can use combinatorics and counting. You count how many lower and upper numbers you have to assign, and do lower * (lower — 1) * (lower — 2) *... *1 and upper! as well. There are some blocks that are just 0 though, [0,0], for those you can use a lower and upper but also you can do [U,L] or [L,U], so just count these [0,0] blocks and do 2^(zero_blocks). So you can get this in the end lower! * upper! * 2^zero_blocks. Where I described how to get lower, upper, and zero_blocks clearly I hope.