Show problems as
Classic problem #1004MediumArrayBinary SearchSliding WindowPrefix Sum

Max Consecutive Ones III

Real-world version: Longest Verified Backup Streak
Tracked in this browser only
Read Max Consecutive Ones III on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstSliding Window Maximum/Minimum · Priority Queues, animated step by step

A storage team keeps a nightly integrity log. checks holds one entry per night in chronological order: 1 means that night's snapshot was checked, 0 means the check was skipped.

There is spare capacity to go back and check at most k of the skipped nights, and the team may choose whichever skipped nights it likes.

Report the greatest number of neighbouring nights that can all end up checked once at most k retro-checks have been spent. Spare capacity may go unused, and the nights picked for a retro-check need not sit next to each other.

Examples

Example 1

Input
checks = [1, 1, 0, 1, 1, 0, 1], k = 1
Output
5

Spending the single retro-check on night 2 leaves nights 0 through 4 all checked, five nights wide. Any six neighbouring nights here hold two gaps, which is one retro-check too many.

Example 2

Input
checks = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0], k = 2
Output
7

Retro-checking nights 4 and 5 fills the only gaps inside nights 2 through 8, so seven neighbouring nights end up checked.

Example 3

Input
checks = [0, 0, 0], k = 0
Output
0

Nothing was checked and there is no spare capacity, so no night can be part of a checked block.

Constraints

  • 1 <= checks.length <= 10^5
  • checks[i] is either 0 or 1.
  • 0 <= k <= checks.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_verified_streak(checks: list[int], k: int) -> int:
Java
public int longestVerifiedStreak(int[] checks, int k)

More on the same topics