It is easy to find the minimum/maximum possible number of \(1\)’s (by finding the contiguous subsequence where the number of \(1\)’s minus the number of \(0\)’s is minimum/maximum).

It turns out that everything between the minimum and maximum is achievable.

For example, let \(X\) be the original number of \(1\)’s, \(Y\) be the maximum number of \(1\)’s achievable, which is achieved by flipping \([L, R]\). Now, consider the number of \(1\)’s after flipping (empty)\(,[L,L],[L,L+1],\cdots,[L,R]\). It changes from \(X\) and \(Y\), and adjacent numbers differ by \(1\), so all numbers between \(X\) and \(Y\) must be present.

The same argument applies to the minimum.

The complexity of the solution is \(O(N)\).

Sample Submission (C++)