695. The Longest Run of Ones After Deleting One
Delete exactly ONE element from the array of zeros and ones, then find the longest run of consecutive ones. Print its length.
The deletion is compulsory, so an array of all ones must still lose one.
1 1 0 1 -> 3
0 1 1 1 0 1 1 0 1 -> 5
1 1 1 -> 2
0 0 0 -> 0
## A window with at most one zero
Keep the longest window containing at most one zero. That zero is the element to delete, and everything else in the window is a one.
The answer is the window LENGTH MINUS ONE, always:
· if the window contains a zero, deleting it leaves length - 1 ones
· if the window contains no zero, one of the ones must be deleted anyway, again leaving
length - 1
So the same expression covers both cases, which is why the compulsory deletion needs no special handling.
## The sweep
for hi in 0 .. n-1:
if a[hi] == 0: zeros += 1
while zeros > 1:
if a[lo] == 0: zeros -= 1
lo += 1
best = max(best, hi - lo)
Note hi - lo, not hi - lo + 1. That missing + 1 IS the deletion, and writing the usual
length by reflex is the bug this problem is built around.
## The relationship with problem 683
683 allows up to k zeros to be FLIPPED and wants the window length itself. This allows one
zero to be DELETED and wants one less.
Same window, same invariant, different arithmetic at the end. Noticing that the difference is in the reporting rather than the sweep is the point.
## Boundaries
All zeros answers 0: every window of length 1 reports 1 - 1 = 0.
A single element answers 0, since deleting it leaves nothing.
All ones answers n - 1.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 200000` - each value is `0` or `1`
Input
The first line contains an integer n.
The second line contains n integers, each 0 or 1.
Output
Print one integer, the longest run of ones after deleting exactly one element.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.