题解

思路

把原序列中的 0 看成 $+1$、1 看成 $-1$。

做法

翻转一个区间后，1 的数量相对原来恰好增加这个区间的元素和，因此只需找这种新序列的最大子段和与最小子段和；空区间对应增量 0。用两次 Kadane 扫描即可在线维护二者。

若某个区间取得最大增量，从空区间逐步扩展到它时，相邻增量只相差 1，所以 0 到最大值之间都可达；最小值一侧同理。故所有可达增量构成连续整数区间，答案为最大值减最小值再加 1。

复杂度

时间复杂度为 $O(N)$，空间复杂度为 $O(1)$。