)
先考虑比较暴力的做法。枚举选择的子序列最中间的位置 \(i\)，这样一来根据经典贪心结论，左右两侧都分别需要选 \(\frac k2\) 个（对 \(2\mid k\) 的情况需要处理左边多选一个还是右边多选一个）。对每个值不和 \(i\) 相等的值，求出 \(i\) 左右两侧第一个和其值相同的位置 \(l_j,r_j\)，贪心排序选取就可以做到 \(O(n^2\log n)\)。
考虑优化该算法。容易发现可以去掉在左右两侧分别选 \(\frac k2\) 个数的限制，直接贪心取 \(\min\) 放即可。证明的话考虑一个位置左右两侧的元素个数如果不相同那么一定可以调整到更优，因此最小值一定不会被漏过去。这样就可以优化到 \(O(n^2)\) / \(O(nk)\) 解决。
考虑从左往右扫描位置 \(i\)。注意到对每个值 \(j\)，在 \(i\) 右移一个单位的时候 \(j\) 的贡献的变化必然为 \(-1,0,1\) 中的一个。然后还可以发现若当前元素的值在中心位置之前则贡献的变化为 \(-1\)，在中心位置之后则贡献为 \(1\)。而特殊的，若 \(2\mid k\)，则需要特殊处理：此时存在两个中心，在两个中心变化的过程中该位置的贡献不会变化。
注意到贡献变化相同的位置是一段区间，写一个二阶差分即可 \(O(n)\) 维护答案的变化，可以通过该题。