保持高平均值题解

思路

先把每个元素减去 $x$。原条件就变为：每个完全由已选元素组成、且长度至少为 $2$ 的连续子段，其元素和必须非负。

只检查长度 $2$ 和长度 $3$ 的子段就足够。任意长度至少为 $4$ 的偶数段都能拆成若干个长度为 $2$ 的段；任意长度至少为 $5$ 的奇数段都能拆成一个长度为 $3$ 的段和若干个长度为 $2$ 的段。如果这些短段之和均非负，原长段之和也非负。

因此扫描数组时，选择当前元素是否可行只取决于前两个位置是否被选择，以及对应二元和、三元和是否非负。用四个状态记录前两个位置的选择情况和当前最多选择数即可。

做法

将所有 $a_i$ 替换为 $a_i-x$。状态的两个二进制位分别表示前两个位置是否被选择，状态值表示处理完当前前缀后最多选择了多少个元素。

处理新元素时：

• 不选择它，清空最新一位并保留已有选择数；
• 选择它时，若前一位也被选择，则检查二元和；若前两位都被选择，再检查三元和。全部检查通过后选择数加一。

转移后只保留新的最后两个选择位。初始时还没有处理元素，对应状态值为零。扫描结束后取四个状态中的最大值。

因为所有可能的选择集合都可按位置依次决定选或不选，转移枚举了全部方案。长度二与三的检查既是必要条件，又由分段论证推出所有更长子段也合法，所以状态判定与原题条件等价。

复杂度

每个位置只转移常数个状态，每组数据的时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。