Hi!

While solving Div2 D, I came across another problem (not related to solving the actual problem though) :

Given a binary array A of size N, you are required to remove all the occurrence of 1 in the array only using the following step:

• Select any subarray of size K ( K <= N ) and remove it from the array. After removing it, the adjacent parts (if any) will be joined as a single array.

Let's define Ans as the size remaining array after removing all the occurrence of 1 in A. Find the maximum value of Ans or say that it's impossible.

eg,

A : [1, 0, 0, 1, 0, 0, 1, 1] ,
K = 2
We have, Ans = 2 (In the end 3rd and 6th 0 's in the remaining array, Indexing from 1), multiple answers possible.

A simple greedy solution can be to select a window with a maximum frequency of 1s and remove it, continue doing this until all 1s are gone or say it's impossible. O(n^2), not sure of the correctness though :(

I'd like to hear your approach to this problem.

Thanks in advance!