Longest Ones After Flips - Classic Problems | Repovive

CLS58. Longest Ones After Flips

2s256 MB

Given a binary array, flip at most $k$ zeros to ones. Find the maximum length of a contiguous segment containing only ones after the flips.

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

len_{\max}

Input

8 2
1 0 1 1 0 0 1 1

Explanation

Flip the zeros at positions 5 and 6. Then positions 3 through 8 are all ones, giving length 6.

Output

Input

5 0
1 1 0 1 1

Explanation

No flips are allowed, so the longest existing all-one block has length 2.

Output

Input

4 4
0 0 0 0

Explanation

All four zeros may be flipped, so the entire array becomes a block of length 4.

Output

Given a binary array, flip at most $k$ zeros to ones. Find the maximum length of a contiguous segment containing only ones after the flips.

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

len_{\max}