Ok, I've found relation between n and maximin palindrome number and several optimal patterns that depend on n mod 12. Only one question has left: how to prove all this stuff?

My AC solution is using n mod 6 to determine the optimal solution.

The proof is rather complicated and heavily relies on some particular pattern of length 6. Apart from that, it's just analysing lots and lots of cases.