683. Longest Run of Ones After k Flips
Given an array of 0s and 1s and a number k, you may change at most k
zeros into ones. Print the length of the longest run of consecutive ones you can
produce.
Read it as a window question and it becomes simple: find the longest window
containing at most k zeros. The ones inside cost nothing and the zeros are
what you spend on.
The number of zeros inside a window never falls as the window widens, so once a window holds too many, widening it cannot help and the left edge advances.
This is the same skeleton as problem 682 with a cheaper test, which is why it
comes first. Trying every window is O(n^2); this is O(n) and visits each
index at most twice.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ k ≤ n` - Every value is `0` or `1`.
Input
The first line contains two integers n and k.
The second line contains n space-separated values, each 0 or 1.
Output
Print one integer: the length of the longest run of consecutive ones obtainable by changing at most k zeros.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.