Consider map each color to a number in \(\{1, 2, 3, 4\}\) uniformly random, call this new color sequence as \(K'\), then the probability that the optimal solution still remain valid would be \(\frac{12}{16} \times (\frac{2}{16})^2 = \frac{3}{256}\) because there are \(12\) ways over \(16\) ways that \(K'_{i_3}, K'_{i_4}\) would remain different, and there are \(2\) ways over \(16\) ways that \(K'_{i_1}, K'_{i_2}, K'_{i_3}, K'_{i_4}\) would be pairwise different after fixing \(K'_{i_3}, K'_{i_4}\) (same argument apply for \(K'_{i_3}, K'_{i_4}, K'_{i_5}, K'_{i_6}\)).

So we reduce the number of different color down to \(4\), then we can enumerate \(i_4\) while maintain (the maximum sum of interest using 3 elements before \(i_4\) and form a color set \(\{1, 2, 3, 4\} \setminus \{c\}\), and the last element have color \(d\) (\(d \neq c\))) and (the maximum interest of color \(c\) in a prefix/suffix) for all \(c \in \{1, 2, 3, 4\}\), then we can solve the above problem in \(O(n)\).

Finally, if we run the algorithm enough number of times, we can find the correct answer with high probability. For example, running \(600\) times would have \((1 - \frac{3}{256})^{600} ≈ 8 \times 10^{-4}\) probability to fail.

https://atcoder.jp/contests/abc447/submissions/73728263 (my submission)