Given an array A of 0s and 1s, we may change up to K values from 0 to 1.
Return the length of the longest (contiguous) subarray that contains only 1s. 
 

Example 1:
Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:
Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

 
Note:

1 <= A.length <= 20000
0 <= K <= A.length
A[i] is 0 or 1

Difficulty: MEDIUM
Tags: Data structures

Sorting

Amortized analysis

Range queries
Skill types: Amortized analysis

Sorting

Data structures

Range queries

Starter code:
class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        

Solutions:
class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		hulu = []
		cnt = 0
		num = A[0]
		for x in A:
			if x == num:
				cnt += 1
			else:
				hulu.append([num, cnt])
				cnt = 1
				num = x
		if cnt > 0:
			hulu.append([num, cnt])
		output = 0
		if A[0] == 1:
			start = 0
		else:
			start = 1
			if len(hulu) < 2:
				return min(K, len(A))
		end = start
		usage = 0
		ones = hulu[start][1]
		while end + 2 < len(hulu) and usage + hulu[end + 1][1] <= K:
			usage += hulu[end + 1][1]
			ones += hulu[end + 2][1]
			end += 2
		output = ones + K
		start += 2
		while start < len(hulu):
			ones -= hulu[start - 2][1]
			usage -= hulu[start - 1][1]
			if start > end:
				end = start
				ones = hulu[start][1]
				usage = 0
			while end + 2 < len(hulu) and usage + hulu[end + 1][1] <= K:
				usage += hulu[end + 1][1]
				ones += hulu[end + 2][1]
				end += 2
			output = max(output, ones + K)
			start += 2
		return min(output, len(A))


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		if len(A) - sum(A) <= K:
			return len(A)
		left = right = 0
		for right in range(len(A)):
			if A[right] == 0:
				K -= 1
			if K < 0:
				if A[left] == 0:
					K += 1
				left += 1
		return right - left + 1


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(left, right) = (0, 0)
		alen = len(A)
		while right < alen:
			if A[right] == 0:
				K -= 1
			if K < 0:
				if A[left] == 0:
					K += 1
				left += 1
			right += 1
		return right - left


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(window_start, max_length, max_ones_count) = (0, 0, 0)
		for window_end in range(len(A)):
			if A[window_end] == 1:
				max_ones_count += 1
			if window_end - window_start + 1 - max_ones_count > K:
				if A[window_start] == 1:
					max_ones_count -= 1
				window_start += 1
			max_length = max(max_length, window_end - window_start + 1)
		return max_length


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(i, j, count, res) = (0, 0, 0, 0)
		while j < len(A):
			if A[j] == 0:
				count += 1
			while count > K:
				if A[i] == 0:
					count -= 1
				i += 1
			res = max(res, j - i + 1)
			j += 1
		return res


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(start, end) = (0, 0)
		max_len = 0
		numzeros = 0
		while end < len(A):
			if A[end] == 0:
				numzeros += 1
			while numzeros > K:
				if A[start] == 0:
					numzeros -= 1
				start += 1
			max_len = max(max_len, end - start + 1)
			end += 1
		return max_len


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		res = 0
		(start, end) = (0, 0)
		cnt = 0
		while end < len(A) and start < len(A):
			if A[end] == 1:
				res = max(res, end - start + 1)
				end += 1
			elif A[end] == 0 and cnt < K:
				res = max(res, end - start + 1)
				cnt += 1
				end += 1
			else:
				if A[start] == 0 and K > 0:
					cnt -= 1
				start += 1
				if start > end:
					end = start
		return res


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		maxConsecutiveOnes = 0
		windowStart = 0
		currZeroes = 0
		for windowEnd in range(len(A)):
			if A[windowEnd] == 0:
				currZeroes += 1
			while currZeroes > K:
				if A[windowStart] == 0:
					currZeroes -= 1
				windowStart += 1
			maxConsecutiveOnes = max(maxConsecutiveOnes, windowEnd - windowStart + 1)
		return maxConsecutiveOnes


class Solution:

	def longestOnes(self, A: List[int], k: int) -> int:
		leftPtr = 0
		rightPtr = 0
		windowSize = []
		while rightPtr <= len(A) - 1:
			if A[rightPtr] == 0:
				k -= 1
			if k < 0:
				if A[leftPtr] == 0:
					k += 1
				leftPtr += 1
			rightPtr += 1
		return rightPtr - leftPtr


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		start = 0
		end = 0
		l = len(A)
		count = 0
		max_len = 0
		while end < l:
			if A[end] == 1:
				max_len = max(max_len, end - start + 1)
				end = end + 1
			elif count < K:
				max_len = max(max_len, end - start + 1)
				count = count + 1
				end = end + 1
			else:
				while start <= end and count >= K:
					if A[start] == 0:
						count = count - 1
					start = start + 1
		return max_len


def solve(arr, n, k):
	prefix = [0]
	for i in range(0, n):
		if arr[i] == 0:
			prefix.append(prefix[-1] + 1)
		else:
			prefix.append(prefix[-1])
	low = 0
	high = n + 1
	ans = 0
	while low < high:
		f = 0
		mid = low + (high - low) // 2
		for i in range(mid, n + 1):
			if prefix[i] - prefix[i - mid] <= k:
				ans = max(ans, mid)
				f = 1
		if f == 1:
			low = mid + 1
		else:
			high = mid
	return ans

class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		return solve(A, len(A), K)


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(ans, i, c) = (0, 0, [])
		for j in range(len(A)):
			if A[j] == 0:
				c += (j,)
			while len(c) > K:
				i = c.pop(0) + 1
			ans = max(ans, j - i + 1)
		return ans


class Solution:

	def longestOnes(self, A: List[int], k: int) -> int:
		res = 0
		i = j = 0
		move = 1
		while i < len(A) and j < len(A):
			if move == 1:
				if A[j] == 0:
					if k == 0:
						move = 0
						print(i, j)
						res = max(res, j - i)
					k -= 1
				j += 1
			if move == 0:
				if A[i] == 0:
					k += 1
					move = 1
				i += 1
		return max(res, j - i)


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(start, end) = (0, 0)
		for end in range(len(A)):
			if A[end] == 0:
				K -= 1
			if K < 0:
				if A[start] == 0:
					K += 1
				start += 1
		return end - start + 1


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		ans = 0
		l = 0
		r = 0
		prefix = [0 for i in range(len(A))]
		for i in range(len(A)):
			if i == 0:
				prefix[i] = A[0]
			else:
				prefix[i] = A[i] + prefix[i - 1]
		if K >= len(A) - prefix[-1]:
			return len(A)
		while r < len(A) and l < len(A):
			while r < len(A):
				if l == 0:
					this_sum = prefix[r]
				else:
					this_sum = prefix[r] - prefix[l - 1]
				if r - l + 1 - this_sum > K:
					r -= 1
					break
				r += 1
			if r >= len(A):
				if r - l > ans:
					ans = r - l
				break
			if r - l + 1 > ans:
				ans = r - l + 1
			while l < len(A) and A[l] == 1:
				l += 1
			l += 1
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		count = 0
		maxCount = -1
		first = 0
		for i in range(len(A)):
			if A[i] == 0 and K != 0:
				count += 1
				K -= 1
			elif A[i] == 0 and K == 0:
				while A[first] != 0:
					first += 1
					count -= 1
				first += 1
			else:
				count += 1
			maxCount = max(maxCount, count)
		return maxCount


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(i, j) = (0, 0)
		count = 0
		out = 0
		for i in range(len(A)):
			if A[i] == 0:
				count += 1
			while count > K and j < len(A):
				if A[j] == 0:
					count -= 1
				j += 1
			out = max(out, i - j + 1)
		return out


class Solution:

	def longestOnes(self, a: List[int], K: int) -> int:
		i = 0
		j = 0
		ml = 0
		while i < len(a):
			if a[i] == 0:
				K -= 1
			while K < 0:
				if a[j] == 0:
					K += 1
				j += 1
			ml = max(ml, i - j + 1)
			i += 1
		return ml


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		if not A:
			return 0
		best_window_len = 0
		(p, q) = (0, 0)
		num_zeros = 0
		while q < len(A):
			if A[q] == 0:
				num_zeros += 1
			if num_zeros > K:
				best_window_len = max(q - p, best_window_len)
				while num_zeros > K:
					if A[p] == 0:
						num_zeros -= 1
					p += 1
			q += 1
		best_window_len = max(q - p, best_window_len)
		return best_window_len


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		subarrays = []
		start = -1
		i = 0
		while i < len(A):
			if A[i] == 1:
				if start == -1:
					start = i
			elif start != -1:
				subarrays.append([start, i])
				start = -1
			i += 1
		if A[i - 1] == 1:
			subarrays.append([start, i])
		print(subarrays)
		if K == 0:
			result = 0
			for arr in subarrays:
				if arr[1] - arr[0] > result:
					result = arr[1] - arr[0]
			return result
		window = []
		start = []
		end = []
		result = 0
		for i in range(len(A)):
			if A[i] == 0:
				if len(window) == K:
					window.pop(0)
				window.append(i)
				left = window[0] - 1
				right = window[-1] + 1
				while left >= 0 and A[left] != 0:
					left -= 1
				while right < len(A) and A[right] != 0:
					right += 1
				if right - left > result:
					result = right - left
		return result - 1


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		start = end = 0
		res = 0
		map = collections.defaultdict(int)
		while end < len(A):
			map[A[end]] += 1
			while end - start + 1 - map[1] > K:
				map[A[start]] -= 1
				start += 1
			res = max(res, end - start + 1)
			end += 1
		return res


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		begins = [-1] * (K + 1)
		cur = [0] * (K + 1)
		maxL = 0
		curMax = 0
		for (i, a) in enumerate(A):
			if a == 0:
				maxL = max(maxL, curMax)
				begins.pop(0)
				begins.append(i)
				curMax -= cur.pop(0)
				curMax += 1 if begins[0] == -1 else 0
				cur.append(0)
			else:
				cur[-1] += 1
				curMax += 1
		return max(maxL, curMax)


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		right = 0
		for i in range(len(A)):
			if A[i] == 0:
				A[i] = 1
			else:
				A[i] = 0
		tot = A[0]
		res = 0
		for left in range(len(A)):
			while tot <= K:
				right = right + 1
				if right >= len(A):
					break
				tot = tot + A[right]
			res = max(res, right - left)
			if right >= len(A) - 1:
				break
			if A[left] == 1:
				tot = tot - 1
		return res


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		k = K
		j = ans = 0
		for i in range(len(A)):
			if not A[i]:
				k -= 1
			while k < 0:
				if not A[j]:
					k += 1
				j += 1
			ans = max(ans, i - j + 1)
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(i, res) = (0, 0)
		for j in range(len(A)):
			K -= 1 - A[j]
			while K < 0:
				K += 1 - A[i]
				i += 1
			res = max(res, j - i + 1)
		return res


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(left, right) = (0, 0)
		max_window = 0
		zero_positions = []
		num_violations = 0
		while right < len(A):
			if A[right] == 0:
				num_violations += 1
				zero_positions.append(right)
			if num_violations > K:
				left = zero_positions[0] + 1
				zero_positions.pop(0)
				num_violations -= 1
			right += 1
			max_window = max(max_window, right - left)
		return max_window


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		z_count = 0
		l = 0
		result = 0
		for i in range(len(A)):
			if not A[i]:
				z_count += 1
			if z_count <= K:
				result = max(result, i - l + 1)
			while l < i and z_count > K:
				if not A[l]:
					z_count -= 1
				l += 1
		return result


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		longest = start = end = zeroes = 0
		while end < len(A):
			num = A[end]
			if not num:
				zeroes += 1
			end += 1
			while zeroes > K:
				if A[start] == 0:
					zeroes -= 1
				start += 1
			longest = max(longest, end - start)
		return longest


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		res = 0
		(i, j, N) = (0, 0, len(A))
		remaining = K if A[i] == 1 else K - 1
		while i < N:
			if i > j:
				j = i
				remaining = K if A[i] == 1 else K - 1
			while j + 1 < N and remaining >= 0:
				if A[j + 1] == 0:
					if remaining > 0:
						remaining -= 1
					else:
						break
				j += 1
				res = max(res, j - i + 1)
			if A[i] == 0:
				remaining += 1
			i += 1
		return res


class Solution:

	def longestOnes(self, x: List[int], K: int) -> int:
		buf = collections.deque()
		n = len(x)
		i = 0
		unused = K
		start = -1
		maxlen = float('-inf')
		while i < n:
			if x[i] == 0:
				if unused > 0:
					buf.append(i)
					unused -= 1
					maxlen = max(i - start, maxlen)
				elif buf:
					start = buf.popleft()
					maxlen = max(i - start, maxlen)
					buf.append(i)
				else:
					maxlen = max(i - 1 - start, maxlen)
					start = i
			else:
				maxlen = max(i - start, maxlen)
			i += 1
		return maxlen if n > 0 else n


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		l = 0
		for r in range(len(A)):
			if A[r] == 0:
				K -= 1
			if K < 0:
				if A[l] == 0:
					K += 1
				l += 1
		return r - l + 1


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		lo = 0
		hi = len(A)
		A = [0] + [1 - x for x in A]
		n = len(A)
		for i in range(1, n):
			A[i] += A[i - 1]
		while lo < hi:
			mid = (lo + hi + 1) // 2
			if min((A[i] - A[i - mid] for i in range(mid, len(A)))) <= K:
				lo = mid
			else:
				hi = mid - 1
		return lo


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		if not A:
			return 0
		window = 0
		start = 0
		max_ones = 0
		for (it, value) in enumerate(A):
			window += value
			if it - start + 1 > window + K:
				window -= A[start]
				start += 1
			max_ones = max(max_ones, window + K)
		return min(max_ones, len(A))


class Solution:

	def longestOnes(self, A: List[int], k: int) -> int:
		ans = 0
		i = 0
		for (j, c) in enumerate(A):
			k -= 1 - c
			if k < 0:
				k += 1 - A[i]
				i += 1
				ans = max(ans, j - i + 1)
		return max(ans, j - i + 1)


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		left = 0
		right = 0
		maxlength = 0
		hashmap = {}
		count = 0
		while right < len(A):
			hashmap[A[right]] = hashmap.get(A[right], 0) + 1
			while A[right] == 0 and hashmap[A[right]] > K:
				hashmap[A[left]] -= 1
				left += 1
			maxlength = max(maxlength, right - left + 1)
			right += 1
		return maxlength


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		left = 0
		right = 0
		contains = 0
		max_len = 0
		while right < len(A):
			if A[right] == 0:
				contains += 1
				if contains > K:
					while contains > K:
						if A[left] == 0:
							contains -= 1
						left += 1
			max_len = max(max_len, right - left + 1)
			right += 1
		return max_len


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		l = len(A)
		end = 0
		start = 0
		ans = 0
		count = 0
		for i in range(l):
			if A[i] == 1:
				count += 1
			if end - start + 1 - count <= K:
				ans = max(ans, end - start + 1)
			else:
				if A[start] == 1:
					count -= 1
				start += 1
			end += 1
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(lo, hi) = (0, 0)
		zmax = 0
		n_k = 0
		while hi < len(A):
			if A[hi] == 0:
				n_k += 1
			while n_k > K:
				if A[lo] == 0:
					n_k -= 1
				lo += 1
			zmax = max(zmax, hi - lo + 1)
			hi += 1
		return zmax


class Solution:

	def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
		if len(nums) == 0:
			return 0
		left = 0
		while left < len(nums) and nums[left] != 1:
			left += 1
		right = left
		while right + 1 < len(nums) and nums[right + 1] == 1:
			right += 1
		if right == len(nums):
			return 0
		maxOnes = right - left + 1
		while left < len(nums):
			left = right + 1
			while left < len(nums) and nums[left] != 1:
				left += 1
			right = left
			while right + 1 < len(nums) and nums[right + 1] == 1:
				right += 1
			maxOnes = max(maxOnes, right - left + 1)
		return maxOnes

	def longestOnes(self, A: List[int], K: int) -> int:
		if K == 0:
			return self.findMaxConsecutiveOnes(A)
		if len(A) == 0:
			return 0
		(left, right) = (0, 0)
		if A[right] == 0:
			K -= 1
		while right + 1 < len(A) and K > 0:
			right += 1
			if A[right] == 0:
				K -= 1
		while right + 1 < len(A) and A[right + 1] == 1:
			right += 1
		maxSize = right - left + 1
		while right < len(A):
			while left < len(A) and A[left] != 0:
				left += 1
			if left < len(A):
				left += 1
			else:
				return maxSize
			right += 1
			while right + 1 < len(A) and A[right + 1] == 1:
				right += 1
			maxSize = max(maxSize, right - left + 1)
		return maxSize


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		slow = fast = 0
		maxOnes = -1
		lastZero = collections.deque()
		while fast < len(A):
			if A[fast] == 0:
				lastZero.append(fast)
				if len(lastZero) > K:
					slow = lastZero.popleft() + 1
			fast += 1
			maxOnes = max(maxOnes, fast - slow)
		if maxOnes == -1:
			return len(A)
		return maxOnes


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(st, ed) = (0, 0)
		ans = 0
		longest = 0
		k = 0
		while ed < len(A):
			while ed < len(A):
				if A[ed] == 1:
					longest += 1
				elif k < K:
					k += 1
					longest += 1
				else:
					break
				ed += 1
			ans = max(longest, ans)
			while st <= ed and st < len(A):
				longest -= 1
				if A[st] == 0:
					k -= 1
					st += 1
					break
				st += 1
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(start, end, max_length, num_0) = (0, 0, 0, int(not A[0]))
		while end < len(A) - 1:
			if num_0 > K:
				if A[start] == 0:
					num_0 -= 1
				start += 1
			end += 1
			if A[end] == 0:
				num_0 += 1
			if num_0 <= K:
				max_length = end - start + 1
		return max_length


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		startWindow = 0
		maxLength = 0
		nZerosInsideWindow = 0
		for (endWindow, el) in enumerate(A):
			nZerosInsideWindow += el == 0
			while nZerosInsideWindow > K:
				firstElement = A[startWindow]
				nZerosInsideWindow -= firstElement == 0
				startWindow += 1
			maxLength = max(maxLength, endWindow - startWindow + 1)
		return maxLength


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		n = len(A)
		if n == 0:
			return 0
		head = 0
		tail = 0
		num_zeros = 0
		max_subseq = 0
		while head < n:
			if A[head] == 1:
				head += 1
			else:
				num_zeros += 1
				max_subseq = max(max_subseq, head - tail)
				if num_zeros > K:
					while A[tail] == 1:
						tail += 1
					tail += 1
					num_zeros -= 1
				head += 1
		max_subseq = max(max_subseq, n - tail)
		return max_subseq


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		allowance = K
		currSum = 0
		left = 0
		maxSum = 0
		for i in range(len(A)):
			if A[i] == 1:
				currSum += 1
			else:
				allowance -= 1
				while allowance < 0:
					if A[left] == 1:
						currSum -= 1
					else:
						allowance += 1
					left += 1
			maxSum = max(maxSum, K - allowance + currSum)
		return maxSum


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		i = 0
		res = 0
		for (j, a) in enumerate(A):
			if a == 0:
				K -= 1
			while K < 0:
				if A[i] == 0:
					K += 1
				i += 1
			else:
				res = max(res, j - i + 1)
		return res


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		if A == None or len(A) == 0 or K == None:
			return 0
		if len(A) <= K:
			return K
		left = 0
		flip = 0
		maxlength = 0
		for (i, num) in enumerate(A):
			if A[i] == 0:
				flip += 1
			if flip <= K:
				maxlength = max(maxlength, i - left + 1)
			while left < i and flip > K:
				if A[left] == 0:
					flip -= 1
				left += 1
		return maxlength


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(count, n, l) = (0, len(A), 0)
		ans = 0
		for r in range(n):
			count += 1 - A[r]
			while count > K:
				count -= 1 - A[l]
				l += 1
			ans = max(ans, r - l + 1)
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(windowstart, curr0, res) = (0, 0, 0)
		currwindow = {1: 0, 0: 0}
		for windowend in range(len(A)):
			currwindow[A[windowend]] += 1
			curr0 = currwindow[0]
			if curr0 > K:
				currwindow[A[windowstart]] -= 1
				windowstart += 1
			res = max(res, windowend - windowstart + 1)
		return res


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		count_1 = 0
		zero_inx = []
		res = 0
		zero_before = -1
		for i in range(len(A)):
			if A[i] == 1:
				count_1 += 1
			else:
				zero_inx.append(i)
				if K > 0:
					K -= 1
					count_1 += 1
				elif K == 0:
					res = max(res, count_1)
					first_0 = zero_inx.pop(0)
					count_1 -= first_0 - zero_before - 1
					zero_before = first_0
		res = max(res, count_1)
		return res


class Solution:

	def longestOnes(self, arr: List[int], k: int) -> int:
		start_index = 0
		longest_ones = 0
		max_length = 0
		for end_index in range(len(arr)):
			if arr[end_index] == 1:
				longest_ones += 1
			if longest_ones + k <= end_index - start_index:
				if arr[start_index] == 1:
					longest_ones -= 1
				start_index += 1
			max_length = max(max_length, end_index - start_index + 1)
		return max_length


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		i = 0
		j = 0
		numZeros = 0
		bestSize = 0
		while j < len(A):
			if A[j] == 1:
				pass
			elif A[j] == 0:
				numZeros += 1
				while numZeros > K:
					if i >= 0 and A[i] == 0:
						numZeros -= 1
					i += 1
			bestSize = max(bestSize, j - i + 1)
			j += 1
		return bestSize


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(s, e) = (0, 0)
		r_k = K
		result = 0
		while e < len(A):
			if A[e] == 0:
				r_k -= 1
			while r_k < 0:
				if A[s] == 0:
					r_k += 1
				s += 1
			result = max(result, e - s + 1)
			e += 1
		return result


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		res = -1
		(start, count) = (0, 0)
		for i in range(len(A)):
			if A[i] == 1:
				count += 1
			while i - start + 1 - count > K:
				if A[start] == 1:
					count -= 1
				start += 1
			res = max(res, i - start + 1)
		return res


class Solution:

	def longestOnes(self, s: List[int], k: int) -> int:
		l = 0
		c_frequency = {0: 0, 1: 0}
		longest_str_len = 0
		for r in range(len(s)):
			if s[r] == 0:
				c_frequency[0] += 1
			else:
				c_frequency[1] += 1
			cells_count = r - l + 1
			if c_frequency[0] <= k or c_frequency[0] == 0:
				longest_str_len = max(longest_str_len, cells_count)
			else:
				if c_frequency[s[l]] != 0:
					c_frequency[s[l]] -= 1
				l += 1
		return longest_str_len


import bisect

class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		ans = countzeroes = 0
		counter = {0: -1}
		for (i, num) in enumerate(A):
			if num == 0:
				countzeroes += 1
			if countzeroes not in counter:
				counter[countzeroes] = i
			j = counter[max(0, countzeroes - K)]
			ans = max(ans, i - j)
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(l, r) = (0, -1)
		optim = 0
		while r < len(A):
			while r < len(A):
				r += 1
				if r == len(A):
					break
				if A[r] == 0:
					K -= 1
				if K < 0:
					break
				else:
					optim = max(optim, r - l + 1)
			if r == len(A):
				break
			while l < r:
				if A[l] == 0:
					K += 1
				l += 1
				if K >= 0:
					break
		return optim


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		count = maxS = j = 0
		for (i, a) in enumerate(A):
			if a == 0:
				count += 1
			while j < len(A) and count > K:
				if A[j] == 0:
					count -= 1
				j += 1
			maxS = max(maxS, i - j + 1)
		return maxS


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(windowstart, most_common, res) = (0, 0, 0)
		currentwindow = {1: 0, 0: 0}
		for windowend in range(len(A)):
			currentwindow[A[windowend]] += 1
			most_common = currentwindow[1]
			if windowend - windowstart + 1 - most_common > K:
				currentwindow[A[windowstart]] -= 1
				windowstart += 1
			res = max(res, windowend - windowstart + 1)
		return res


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(zeros, ones, max_len) = (0, 0, 0)

		def element_found(element, inc):
			nonlocal zeros, ones, max_len
			if element == 0:
				zeros += inc
			else:
				ones += inc
		start = 0
		for element in A:
			element_found(element, 1)
			while zeros > K:
				(start, start_element) = (start + 1, A[start])
				element_found(start_element, -1)
			max_len = max(max_len, zeros + ones)
		return max_len


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		if not A:
			return 0
		n = len(A)
		cur_max = 0
		counter = 0
		index = []
		prev = -1
		for i in range(n):
			if A[i] == 1:
				counter += 1
			elif K > 0:
				K -= 1
				counter += 1
				index.append(i)
			elif index:
				counter += 1
				temp = index.pop(0)
				counter -= temp - prev
				prev = temp
				index.append(i)
			else:
				counter = 0
			cur_max = max(cur_max, counter)
		return cur_max


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		left = 0
		right = 0
		k = K
		max_ans = 0
		so_far = 0
		while right < len(A):
			if A[right] == 1:
				right += 1
			elif k > 0:
				right += 1
				k -= 1
			else:
				if A[left] == 0:
					k += 1
				left += 1
			max_ans = max(max_ans, right - left)
		return max_ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		zeros_indices = []
		for i in range(len(A)):
			if A[i] == 0:
				zeros_indices.append(i)
		longest_ones = 0
		longest_yet = 0
		for i in range(len(A)):
			if A[i] == 1:
				longest_yet += 1
				longest_ones = max(longest_ones, longest_yet)
			else:
				longest_yet = 0
		if K == 0:
			return longest_ones
		if K >= len(zeros_indices):
			return len(A)
		zero_order = -1
		for i in range(len(A)):
			if A[i] == 0:
				zero_order += 1
				right_cons_ones = left_cons_ones = 0
				if zero_order + K < len(zeros_indices):
					nxt = zero_order + K
					right_cons_ones = zeros_indices[nxt] - zeros_indices[zero_order]
				else:
					nxt = len(zeros_indices) - 1
					right_cons_ones = zeros_indices[nxt] - zeros_indices[zero_order]
					right_cons_ones += len(A) - zeros_indices[nxt]
				if not zero_order == 0:
					left_cons_ones = zeros_indices[zero_order] - zeros_indices[zero_order - 1] - 1
				longest_ones = max(longest_ones, right_cons_ones + left_cons_ones)
		return longest_ones


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		hash_count = dict()
		hash_count[1] = 0
		start = 0
		max_count = 0
		max_result = 0
		for end in range(len(A)):
			if A[end] == 1:
				hash_count[A[end]] += 1
			max_count = max(max_count, hash_count[1])
			if max_count + K < end - start + 1:
				if A[start] == 1 and hash_count.get(1):
					hash_count[1] -= 1
				start += 1
			max_result = max(max_result, end - start + 1)
		return max_result


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		max_length = 0
		start = 0
		end = 1
		zeros = 0
		if len(A) == 0:
			return 0
		if len(A) == 1:
			return 1
		zeros = 2 - sum(A[:2])
		while end < len(A):
			valid = zeros <= K
			if valid:
				max_length = max(max_length, end - start + 1)
				end += 1
				if end == len(A):
					return max_length
				if A[end] == 0:
					zeros += 1
			else:
				if A[start] == 0:
					zeros -= 1
				start += 1
		return max_length


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		K_original = K
		i = 0
		ans = 0
		curr = 0
		j = 0
		while j < len(A):
			if A[j] == 1 or K > 0:
				curr += 1
			else:
				curr = 0
			K -= 1 if A[j] == 0 and K > 0 else 0
			j += 1
			ans = max(curr, ans)
			if K_original > 0 and K == 0:
				while j < len(A) and A[j] == 1:
					curr += 1
					j += 1
				ans = max(curr, ans)
				while i <= j and i < len(A) and (K == 0):
					if A[i] == 0:
						K += 1
					i += 1
					curr -= 1
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(left, right) = (0, 0)
		k = 0
		flipped = set()
		longest = 0
		while right < len(A):
			if A[right] == 1:
				longest = max(longest, right - left + 1)
				right += 1
			elif A[right] == 0 and k < K:
				flipped.add(right)
				longest = max(longest, right - left + 1)
				right += 1
				k += 1
			elif left == right:
				right += 1
				left += 1
			else:
				if left in flipped:
					flipped.discard(left)
					k -= 1
				left += 1
		return longest


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		ct = Counter()
		(pt, max_len) = (0, 0)
		for (i, elem) in enumerate(A):
			ct[elem] += 1
			if ct[0] <= K:
				max_len = max(max_len, i - pt + 1)
			if ct[0] > K:
				ct[A[pt]] -= 1
				pt += 1
		return max_len


from collections import deque

class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		substited_indexes = deque()
		start = 0
		best = 0
		index = 0
		while index < len(A):
			num = A[index]
			if num == 0:
				if K > 0:
					K -= 1
					A[index] = 1
					substited_indexes.append(index)
				elif K == 0 and len(substited_indexes) == 0:
					start = index + 1
				else:
					start = substited_indexes.popleft()
					A[start] = 0
					start += 1
					K += 1
					continue
			index += 1
			best = max(best, index - start)
		return best


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		max_length = 0
		start = 0
		end = 1
		ones = 1
		if len(A) == 0:
			return 0
		if len(A) == 1:
			return 1
		ones = A[0] + A[1]
		while end < len(A):
			valid = end - start + 1 - ones <= K
			if valid:
				max_length = max(max_length, end - start + 1)
				end += 1
				if end == len(A):
					return max_length
				ones += A[end]
			else:
				ones -= A[start]
				start += 1
		return max_length


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(answer, length) = (0, 0)
		inds = []
		for (i, num) in enumerate(A):
			if num == 1:
				length += 1
			elif len(inds) < K:
				inds.append(i)
				length += 1
			elif K == 0:
				length = 0
			else:
				last_index = inds.pop(0)
				inds.append(i)
				length = i - inds[0] + (inds[0] - last_index)
			answer = max(answer, length)
		return answer


import bisect

class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		ans = 0
		countzeroes = 0
		prefix = []
		for (i, num) in enumerate(A):
			prefix.append(countzeroes)
			if num == 0:
				countzeroes += 1
			j = bisect.bisect_left(prefix, countzeroes - K)
			ans = max(ans, i - j + 1)
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		counter = 0
		i = 0
		j = 0
		res = 0
		for i in range(0, len(A)):
			if A[i] == 0:
				counter += 1
			while counter > K and j < len(A):
				if A[j] == 0:
					counter -= 1
				j += 1
			res = max(res, i - j + 1)
			print(res)
		return res


class Solution:

	def longestOnes(self, A, K: int) -> int:
		ans = count = 0
		j = 0
		for i in range(len(A)):
			if i > 0 and A[i - 1] == 0:
				count -= 1
			while j < len(A) and (A[j] or count < K):
				if A[j] == 1:
					j += 1
				elif count < K:
					count += 1
					j += 1
			ans = max(ans, j - i)
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		l = 0
		r = 0
		max_count = K
		while l < len(A) and r < len(A):
			while r < len(A):
				if A[r] == 1:
					r += 1
				elif K > 0:
					r += 1
					K -= 1
				else:
					break
			if r - l + 1 > max_count:
				max_count = r - l
			print(l, r, max_count)
			if A[l] == 0:
				K += 1
			l += 1
		return max_count


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		hashMap = {}
		windowStart = 0
		m = 0
		hashMap[1] = 0
		for windowEnd in range(len(A)):
			if A[windowEnd] not in hashMap:
				hashMap[A[windowEnd]] = 0
			hashMap[A[windowEnd]] += 1
			while sum(hashMap.values()) - hashMap[1] > K:
				hashMap[A[windowStart]] -= 1
				windowStart += 1
			m = max(m, windowEnd - windowStart + 1)
		return m


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		left = 0
		maxLen = 0
		oneFreq = 0
		maxFreq = 0
		for right in range(len(A)):
			oneFreq += A[right]
			maxFreq = max(maxFreq, oneFreq)
			if right - left + 1 - maxFreq > K:
				oneFreq -= A[left]
				left += 1
			maxLen = max(maxLen, right - left + 1)
		return maxLen


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(i, j, n) = (0, 0, len(A))
		for x in A:
			j += 1
			if x == 0:
				K -= 1
			if K < 0:
				if A[i] == 0:
					K += 1
				i += 1
		return j - i


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		ans = 0
		lo = 0
		hi = 0
		d = collections.defaultdict(int)
		while hi < len(A):
			d[A[hi]] += 1
			while d[0] > K:
				d[A[lo]] -= 1
				if d[A[lo]] == 0:
					del d[A[lo]]
				lo += 1
			ans = max(ans, hi - lo + 1)
			hi += 1
		return ans


class Solution:

	def longestOnes(self, arr: List[int], k: int) -> int:
		hashmap = dict()
		max_len = length = start_index = 0
		hashmap[0] = 0
		hashmap[1] = 0
		for i in arr:
			hashmap[i] += 1
			if hashmap[0] > k:
				hashmap[arr[start_index]] -= 1
				start_index += 1
			max_len = max(max_len, sum(hashmap.values()))
		return max_len


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(left, right) = (0, 0)
		(n, c1, c0) = (len(A), 0, 0)
		ans = 0
		while True:
			if c0 <= K:
				ans = max(ans, right - left)
				if right < n:
					right += 1
					x = A[right - 1]
					if x:
						c1 += 1
					else:
						c0 += 1
				else:
					return ans
			else:
				x = A[left]
				left += 1
				if x:
					c1 -= 1
				else:
					c0 -= 1


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		count = 0
		max_count = 0
		buf = K
		l = r = 0
		needs_buf = False
		while l < len(A) and r < len(A):
			if A[r] == 1:
				count += 1
				r += 1
			elif A[r] == 0:
				if buf:
					buf -= 1
					count += 1
					r += 1
				else:
					needs_buf = True
			if needs_buf:
				if A[l] == 0:
					buf += 1
					needs_buf = False
				count -= 1
				l += 1
			if count > max_count:
				max_count = count
		return max_count


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(s, e, z, l) = (0, 0, 0, 0)
		ans = 0
		while e < len(A):
			if A[e] == 0:
				z += 1
			while z > K:
				if A[s] == 0:
					z -= 1
				s += 1
				l -= 1
			l += 1
			ans = max(ans, l)
			e += 1
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		res = 0
		zeros = 0
		n = len(A)
		i = 0
		for j in range(n):
			zeros += A[j] == 0
			if zeros <= K:
				res = max(res, j - i + 1)
			if zeros > K:
				zeros -= A[i] == 0
				i += 1
		return res


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		left = 0
		zeros = 0
		res = 0
		for right in range(len(A)):
			if A[right] == 0:
				zeros += 1
			while zeros > K:
				left += 1
				if A[left - 1] == 0:
					zeros -= 1
			res = max(res, right - left + 1)
		return res


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		result = 0
		zero_allowed = K
		left = 0
		for (right, x) in enumerate(A):
			if x == 0:
				zero_allowed -= 1
			if zero_allowed >= 0 and right - left + 1 > result:
				result = right - left + 1
			while zero_allowed < 0 and right - left + 1 > result:
				if A[left] == 0:
					zero_allowed += 1
				left += 1
		return result


class Solution:

	def longestOnes(self, arr: List[int], k: int) -> int:
		(start, max_length) = (0, 0)
		count_0 = 0
		for end in range(len(arr)):
			if arr[end] == 0:
				count_0 += 1
			while count_0 > k:
				if arr[start] == 0:
					count_0 -= 1
				start += 1
			max_length = max(max_length, end - start + 1)
		return max_length


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		zeroes = []
		count = 0
		maxCount = 0
		for i in range(len(A)):
			if A[i] == 0:
				zeroes.insert(0, i)
			if len(zeroes) > K:
				count = i - zeroes.pop()
			else:
				count += 1
			maxCount = max(maxCount, count)
		return maxCount


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		curr_k = 0
		pointer_start = 0
		pointer_end = 0
		max_ones = 0
		curr_ones = 0
		while pointer_end < len(A):
			if A[pointer_end] == 0:
				if curr_k >= K:
					if A[pointer_start] == 0:
						curr_k -= 1
					pointer_start += 1
					curr_ones -= 1
				else:
					pointer_end += 1
					curr_ones += 1
					curr_k += 1
			else:
				pointer_end += 1
				curr_ones += 1
			max_ones = max(curr_ones, max_ones)
		return max_ones


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		l = 0
		r = 0
		val = 0
		if A[0] == 0:
			val = 1
		maxlength = 0
		while r < len(A) - 1:
			while val <= K and r < len(A) - 1:
				if A[r + 1] == 0:
					val += 1
				r += 1
			if r == len(A) - 1 and val <= K:
				maxlength = max(maxlength, r - l + 1)
			elif val > K:
				maxlength = max(maxlength, r - l)
				while val > K:
					if A[l] == 0:
						val -= 1
					l += 1
		return maxlength


import math
import random
import string
from functools import lru_cache
from operator import truediv
from typing import List
import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List
import numpy as np
import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List

class Solution:

	def longestOnes1(self, A: List[int], K: int) -> int:
		start = 0
		end = 0
		ret = 0
		while end < len(A):
			if A[end] == 1:
				end += 1
			elif K > 0:
				end += 1
				K -= 1
			else:
				if A[start] == 0:
					K += 1
				start += 1
			ret = max(ret, end - start)
		return ret

	def longestOnes(self, A, K):
		i = 0
		for j in range(len(A)):
			K -= 1 - A[j]
			if K < 0:
				K += 1 - A[i]
				i += 1
		return j - i + 1


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		if not A:
			return 0
		ans = 0
		count = [0, 0]
		max_count = 0
		l = 0
		for r in range(len(A)):
			count[A[r]] += 1
			max_count = max(max_count, count[1])
			if r - l + 1 - max_count > K:
				count[A[l]] -= 1
				l += 1
			else:
				ans = max(ans, r - l + 1)
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		le = 0
		for ri in range(len(A)):
			K -= 1 - A[ri]
			print(le, ri)
			if K < 0:
				K += 1 - A[le]
				le += 1
		return ri - le + 1


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		n = len(A)
		res = 0
		(j, count0) = (0, 0)
		for i in range(n):
			if not A[i]:
				count0 += 1
				if count0 > K:
					res = max(res, i - j)
					while A[j]:
						j += 1
					j += 1
					count0 -= 1
		res = max(res, i - j + 1)
		return res


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		i = 0
		j = 0
		maxValue = 0
		numZeros = 0
		while j < len(A):
			if not A[j]:
				if numZeros < K:
					numZeros += 1
					j += 1
				else:
					maxValue = max(maxValue, j - i)
					while i <= j and A[i]:
						i += 1
					i += 1
					j += 1
			else:
				j += 1
		maxValue = max(maxValue, j - i)
		return maxValue


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		maxOnes = 0
		start = 0
		maxZeroes = 0
		for i in range(len(A)):
			if A[i] == 0:
				maxZeroes += 1
			while maxZeroes > K:
				if A[start] == 0:
					maxZeroes -= 1
				start += 1
			maxOnes = max(maxOnes, i - start + 1)
		return maxOnes


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		start = 0
		ans = 0
		nn = [0, 0]
		for (i, a) in enumerate(A):
			nn[a] += 1
			while nn[0] > K:
				nn[A[start]] -= 1
				start += 1
			ans = max(ans, nn[0] + nn[1])
		return ans


import bisect

class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		n = len(A)
		zeros = 0
		dp = [0] * n
		ans = 0
		for i in range(n):
			if A[i] == 0:
				zeros += 1
			dp[i] = zeros
		for i in range(n):
			val = dp[i]
			if A[i] == 1:
				right = bisect.bisect_left(dp, val + K + 1)
			else:
				right = bisect.bisect_left(dp, val + K)
			delta = right - i
			ans = max(ans, delta)
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		queue = []
		i = ans = 0
		for j in range(len(A)):
			if A[j] != 1:
				if len(queue) == K:
					try:
						i = queue.pop(0) + 1
					except:
						i = j + 1
				if len(queue) < K:
					queue.append(j)
			ans = max(ans, j - i + 1)
		return ans


from collections import deque

class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		q = deque()
		cnt = 0
		max_cnt = 0
		for i in range(len(A)):
			if A[i] == 0:
				q.append(i)
				if len(q) > K:
					max_cnt = max(max_cnt, cnt)
					cnt = i - q[0]
					q.popleft()
				else:
					cnt += 1
			else:
				cnt += 1
		max_cnt = max(max_cnt, cnt)
		return max_cnt


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		l = 0
		r = 0
		m = len(A)
		count = 0
		max_count = 0
		while r < m:
			if A[r] == 1:
				count += 1
			while r - l + 1 - count > K:
				if A[l] == 1:
					count -= 1
				l += 1
			max_count = max(r - l + 1, max_count)
			r += 1
		return max_count


class Solution:

	def longestOnes(self, A, K):
		if not A:
			return 0
		n = len(A)
		right = 0
		cnt = 0
		res = 0
		for left in range(n):
			while right <= n - 1 and (cnt < K or A[right] == 1):
				cnt += A[right] == 0
				right += 1
			res = max(res, right - left)
			cnt -= A[left] == 0
		return res


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		pre_sum = [A[0]]
		for i in range(1, len(A)):
			pre_sum.append(pre_sum[-1] + A[i])

		def cal(l, r):
			if l == 0:
				return pre_sum[r]
			else:
				return pre_sum[r] - pre_sum[l - 1]
		l = 0
		r = 0
		ans = K
		while l < len(A):
			while r < len(A) and r - l + 1 - cal(l, r) <= K:
				ans = max(ans, r - l + 1)
				r = r + 1
			if r == len(A):
				break
			while l < len(A) and r - l + 1 - cal(l, r) > K:
				l = l + 1
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		i = j = maxCount = maxlen = 0
		d = {0: 0, 1: 0}
		while i < len(A):
			d[A[i]] += 1
			while d[0] > K:
				d[A[j]] -= 1
				j += 1
			maxlen = max(maxlen, i - j + 1)
			i += 1
		return maxlen


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(i, ans) = (0, 0)
		for (j, num) in enumerate(A):
			if num == 0:
				K -= 1
			while K < 0:
				if A[i] == 0:
					K += 1
				i += 1
			ans = max(ans, j - i + 1)
		return ans
		ans = 0
		(start, end) = (0, 0)
		while end < len(A):
			if A[end] == 1:
				ans = max(ans, end - start + 1)
				end += 1
			elif K != 0:
				ans = max(ans, end - start + 1)
				end += 1
				K -= 1
			else:
				if A[start] == 0:
					K += 1
				start += 1
		return ans


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(le, ri) = (0, 0)
		max_len = 0
		while ri < len(A):
			if A[ri] == 0:
				K -= 1
			ri += 1
			if K >= 0:
				max_len = max(max_len, ri - le)
			print((le, ri))
			while K < 0 and le < ri:
				if A[le] == 0:
					K += 1
				le += 1
		return max_len


class Solution:

	def longestOnes(self, A: List[int], K: int) -> int:
		(left, right) = (0, 0)
		num_zeros = 0
		window_size = 0
		while right < len(A):
			if A[right] == 0:
				num_zeros += 1
			while num_zeros > K:
				if A[left] == 0:
					num_zeros -= 1
				left += 1
			window_size = max(window_size, right - left + 1)
			right += 1
		return window_size