Given an array A[] consisting of 0’s and 1’s. A flip operation is one in which you turn 1 into 0 and a 0 into 1. You have to do at most one “Flip” operation of any subarray. Formally, select a range (l, r) in the array A[], such that (0 ≤ l ≤ r < n) holds and flip the elements in this range to get the maximum ones in the final array. You can possibly make zero operations to get the answer.
 
Example 1:
Input:
N = 5
A[] = {1, 0, 0, 1, 0} 
Output:
4
Explanation:
We can perform a flip operation in the range [1,2]
After flip operation array is : [ 1 1 1 1 0 ]
Count of one after fliping is : 4
[Note: the subarray marked in bold is the flipped subarray]
 
Example 2:
Input:
N = 7
A[] = {1, 0, 0, 1, 0, 0, 1}
Output:
6
Explanation:
We can perform a flip operation in the range [1,5]
After flip operation array is : [ 1 1 1 0 1 1 1]
Count of one after fliping is : 6
[Note: the subarray marked in bold is the flipped subarray]
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxOnes() which takes the array A[] and its size N as inputs and returns the maximum number of 1's you can have in the array after atmost one flip operation.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ N ≤ 10^{4}
0 ≤ A[i] ≤ 1

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3

class Solution:
    def maxOnes(self, a, n):
        # Your code goes here

Solutions:
class Solution:

	def maxOnes(self, a, n):
		ones = 0
		sum = 0
		maxsum = 0
		for i in range(n):
			if a[i] == 1:
				ones += 1
			if a[i] == 1:
				val = -1
			else:
				val = 1
			sum = sum + val
			maxsum = max(sum, maxsum)
			if sum < 0:
				sum = 0
		return maxsum + ones


class Solution:

	def maxOnes(self, a, n):
		mx = 0
		c = 0
		x = a.count(1)
		for i in range(n):
			if a[i] == 0:
				a[i] = 1
			else:
				a[i] = -1
		for i in range(n):
			c += a[i]
			mx = max(mx, c)
			if c < 0:
				c = 0
		return mx + x


class Solution:

	def maxOnes(self, a, n):
		ones = 0
		sum = 0
		max_sum = 0
		for i in range(n):
			if a[i] == 1:
				ones += 1
			value = -1 if a[i] == 1 else 1
			sum = sum + value
			max_sum = max(sum, max_sum)
			if sum < 0:
				sum = 0
		return max_sum + ones


from collections import *

class Solution:

	def maxOnes(self, a, n):
		c = Counter(a)
		ans = 0
		sub = 0
		for i in range(n):
			if a[i] == 1:
				sub -= 1
			else:
				sub += 1
			if sub < 0:
				sub = 0
			ans = max(sub, ans)
		ans = max(sub, ans)
		return c[1] + ans


class Solution:

	def maxOnes(self, a, n):
		curr = 0
		m = 0
		one = 0
		for i in a:
			if i == 1:
				one += 1
			temp = 1 if i == 0 else -1
			curr = max(temp, curr + temp)
			m = max(m, curr)
		return m + one


class Solution:

	def maxOnes(self, a, n):
		if a.count(1) == n:
			return n
		prefix = [0] * n
		suffix = [0] * n
		if a[0] == 1:
			prefix[0] = 1
		for i in range(1, n):
			prefix[i] += prefix[i - 1] + a[i]
		if a[n - 1] == 1:
			suffix[n - 1] = 1
		for i in range(n - 2, -1, -1):
			suffix[i] += suffix[i + 1] + a[i]
		ans = 0
		j = -1
		tt = 0
		for i in range(n):
			if a[i] == 1:
				tt += 1
			else:
				if tt >= 0:
					tt = -1
					j = i
				else:
					tt -= 1
				if j != -1:
					ans = max(ans, -tt + prefix[i] + suffix[i])
		return ans


class Solution:

	def maxOnes(self, a, n):
		current_sum = 0
		max_sum = 0
		total_one = a.count(1)
		for i in range(0, n):
			if a[i] == 0:
				current_sum = current_sum + 1
			else:
				current_sum = current_sum - 1
			if current_sum > max_sum:
				max_sum = current_sum
			if current_sum < 0:
				current_sum = 0
		return total_one + max_sum


class Solution:

	def maxOnes(self, a, n):
		countof1 = 0
		mx = 0
		diff = 0
		cnt = 0
		for i in range(n):
			if a[i] == 1:
				countof1 += 1
			if a[i] == 0:
				cnt += 1
			else:
				cnt -= 1
			if cnt <= 0:
				cnt = 0
			mx = max(mx, cnt)
			diff = max(diff, mx)
		diff = max(0, diff)
		return countof1 + diff


class Solution:

	def maxOnes(self, a, n):
		maxi = 0
		mini = 0
		count = 0
		for item in a:
			if item:
				count += 1
				maxi = max(maxi, count)
			else:
				count -= 1
				mini = min(mini, count - maxi)
		return sum(a) - mini


import sys

class Solution:

	def maxOnes(self, a, n):
		if a.count(1) == len(a):
			return len(a)
		count = 0
		l = 0
		r = 0
		ltemp = 0
		maxi = -sys.maxsize
		for i in range(n):
			if a[i] == 1:
				count = count - 1
			else:
				count = count + 1
			if count > maxi:
				maxi = count
				l = ltemp
				r = i
			if count < 0:
				count = 0
				ltemp = i + 1
		for i in range(l, r + 1):
			if a[i] == 0:
				a[i] = 1
			else:
				a[i] = 0
		return a.count(1)


class Solution:

	def maxOnes(self, a, n):
		cs = 0
		mx = 0
		for i in range(n):
			if a[i] == 0:
				cs += 1
			else:
				cs -= 1
			mx = max(cs, mx)
			if cs < 0:
				cs = 0
		for i in range(n):
			if a[i] == 1:
				mx += 1
		return mx


class Solution:

	def maxOnes(self, a, n):
		cur_sum = 0
		maxi = 0
		for i in range(n):
			if a[i] == 0:
				cur_sum += 1
			else:
				cur_sum -= 1
			maxi = max(maxi, cur_sum)
			if cur_sum < 0:
				cur_sum = 0
		for i in range(n):
			if a[i] == 1:
				maxi += 1
		return maxi


class Solution:

	def maxOnes(self, a, n):
		sum = 0
		maxsum = 0
		total = 0
		for i in range(len(a)):
			curr = a[i]
			total += a[i]
			if curr == 0:
				curr = 1
			else:
				curr = -1
			sum += curr
			sum = max(curr, sum)
			maxsum = max(sum, maxsum)
		return total + maxsum


class Solution:

	def maxOnes(self, a, n):
		h = [1, -1]
		s = 0
		m_sum = 0
		total = 0
		for i in a:
			total += i
			s += h[i]
			if s > m_sum:
				m_sum = s
			if s < 0:
				s = 0
		return total + m_sum


class Solution:

	def maxOnes(self, a, n):
		ans = 0
		count = 0
		one_count = 0
		for i in a:
			if i == 0:
				count += 1
			else:
				count -= 1
				one_count += 1
			ans = max(ans, count)
			count = max(count, 0)
		return ans + one_count


class Solution:

	def maxOnes(self, arr, n):
		flag = False
		for i in range(0, n):
			if arr[i] == 0:
				arr[i] = 1
				flag = True
			else:
				arr[i] = -1
		if flag == False:
			return n
		subarr = [0, 0]
		start = 0
		end = 0
		prsum = 0
		maxsum = 0
		for i in range(0, n):
			prsum += arr[i]
			if prsum > maxsum:
				maxsum = prsum
				end = i
				subarr[0] = start
				subarr[1] = end
			if prsum < 0:
				prsum = 0
				start = i + 1
		zeros = 0
		cnt = 0
		for i in range(0, n):
			if i >= subarr[0] and i <= subarr[1]:
				if arr[i] == 1:
					zeros += 1
			elif arr[i] == -1:
				cnt += 1
		return zeros + cnt


class Solution:

	def maxOnes(self, a, n):
		arr = a
		diff = 0
		count = 0
		count1 = 0
		for i in range(n):
			if arr[i] == 0:
				count += 1
				diff = max(diff, count)
			else:
				if count != 0:
					count -= 1
				count1 += 1
		if count1 == n:
			return n
		return diff + count1


class Solution:

	def maxOnes(self, a, n):
		arr = a
		maxi = 0
		count = 0
		ones = 0
		for i in range(len(arr)):
			if arr[i] == 0:
				count += 1
				maxi = max(maxi, count)
			else:
				if count != 0:
					count -= 1
				ones += 1
		if ones == len(arr):
			return len(arr)
		return maxi + ones


class Solution:

	def maxSubArraySum(self, a, n):
		(max_so_far, curr_max) = (a[0], a[0])
		for i in range(1, n):
			curr_max = max(a[i], curr_max + a[i])
			max_so_far = max(max_so_far, curr_max)
		max_so_far = max(0, max_so_far)
		return max_so_far

	def maxOnes(self, a, n):
		(i, cnt) = (0, 0)
		for i in range(0, n):
			if a[i] == 0:
				a[i] = 1
			else:
				cnt += 1
				a[i] = -1
		return cnt + self.maxSubArraySum(a, n)


def flipBits(arr, n):
	cnt = 0
	for i in range(n):
		if arr[i] == 1:
			cnt += 1
			arr[i] = -1
		else:
			arr[i] = 1
	s = 0
	ms = 0
	for i in arr:
		s = s + i
		if s > ms:
			ms = s
		if s < 0:
			s = 0
	return ms + cnt

class Solution:

	def maxOnes(self, a, n):
		return flipBits(a, n)


import sys

class Solution:

	def maxOnes(self, a, n):
		m = -sys.maxsize - 1
		count = 0
		one = 0
		for i in range(len(a)):
			if a[i] == 0:
				count += 1
				m = max(count, m)
			else:
				if count != 0:
					count -= 1
				one += 1
		if one == n:
			return n
		return m + one


class Solution:

	def maxOnes(self, a, n):
		org = 0
		curr_max = 0
		max_diff = 0
		for i in range(n):
			if a[i] == 1:
				org += 1
			val = 1 if a[i] == 0 else -1
			curr_max = max(curr_max + val, val)
			max_diff = max(max_diff, curr_max)
		max_diff = max(max_diff, 0)
		return org + max_diff


class Solution:

	def maxOnes(self, a, n):
		maxi = -9999999
		count = 0
		one = 0
		for i in range(n):
			if a[i] == 0:
				count += 1
				maxi = max(count, maxi)
			else:
				if count != 0:
					count -= 1
				one += 1
		if one == n:
			return n
		return maxi + one


class Solution:

	def maxOnes(self, a, n):
		count = 0
		ans = 0
		for num in a:
			if num:
				count -= 1
			else:
				count += 1
			ans = max(count, ans)
			count = max(count, 0)
		return sum(a) + ans


class Solution:

	def maxOnes(self, a, n):
		sum1 = sum(a)
		for i in range(n):
			if a[i] ^ 1 == 0:
				a[i] = -1
			else:
				a[i] = 1
		res = 0
		tempsum = 0
		for i in range(0, n):
			tempsum = max(tempsum + a[i], a[i])
			if tempsum > res:
				res = tempsum
		return res + sum1


class Solution:

	def maxOnes(self, a, n):
		to = 0
		m = 0
		c = 0
		for i in range(n):
			if a[i] == 1:
				to += 1
			val = 0
			if a[i] == 1:
				val = -1
			else:
				val = 1
			c = max(val, c + val)
			m = max(m, c)
		m = max(0, m)
		r = to + m
		return r


class Solution:

	def maxOnes(self, arr, n):
		(cnt0, cnt1, maxcnt) = (0, 0, 0)
		for i in arr:
			if i == 0:
				cnt0 += 1
			else:
				cnt0 -= 1
				cnt1 += 1
			if cnt0 > maxcnt:
				maxcnt = cnt0
			if cnt0 < 0:
				cnt0 = 0
		return cnt1 + maxcnt


class Solution:

	def maxOnes(self, a, n):
		count_ones = 0
		curr_sum = 0
		ans = 0
		for i in range(n):
			if a[i] == 1:
				count_ones += 1
			curr_val = 1 if not a[i] else -1
			curr_sum += curr_val
			ans = max(ans, curr_sum)
			if curr_sum < 0:
				curr_sum = 0
		return count_ones + ans


class Solution:

	def maxOnes(self, a, n):
		for (i, x) in enumerate(a):
			if x == 0:
				a[i] = 1
			else:
				a[i] = -1
		(L, R) = (0, 0)
		(L_, R_) = (-1, -1)
		(cur, maxi) = (0, 0)
		count = 0
		for (i, x) in enumerate(a):
			cur += x
			if cur < 0:
				cur = 0
				L = i + 1
				R = i + 1
			elif cur > maxi:
				(L_, R_) = (L, i)
				maxi = cur
		for i in range(n):
			if i < L_ or i > R_:
				if a[i] == -1:
					count += 1
			elif a[i] == 1:
				count += 1
		return count


class Solution:

	def maxOnes(self, a, n):
		if a.count(1) == len(a):
			return len(a)
		currSum = 0
		maxSum = 0
		li = 0
		ri = 0
		for i in range(n):
			if a[i] == 1:
				tempSum = -1
			else:
				tempSum = 1
			currSum = tempSum + currSum
			if currSum < 0:
				currSum = 0
				li = i + 1
			elif currSum >= maxSum:
				ri = i
				maxSum = currSum
				finalLeft = li
				finalRight = ri
		for j in range(finalLeft, finalRight + 1):
			if a[j] == 0:
				a[j] = 1
			else:
				a[j] = 0
		maxOne = a.count(1)
		return maxOne


class Solution:

	def maxOnes(self, a, n):
		c = 0
		t = 0
		ans = 0
		for i in range(n):
			if a[i] == 0:
				c += 1
			else:
				c -= 1
				t += 1
			if c < 0:
				c = 0
			ans = max(ans, c)
		return ans + t


class Solution:

	def maxOnes(self, a, n):
		maxones = 0
		curr = 0
		maxi = 0
		for i in range(n):
			if a[i] == 1:
				maxones += 1
			val = 1 if a[i] == 0 else -1
			curr = max(curr + val, val)
			maxi = max(maxi, curr)
		return maxi + maxones


class Solution:

	def maxOnes(self, a, n):
		ones = 0
		s = 0
		max_sum = 0
		for i in range(n):
			if a[i] == 1:
				ones += 1
			value = -1 if a[i] == 1 else 1
			s += value
			max_sum = max(s, max_sum)
			if s < 0:
				s = 0
		res = max_sum + ones
		return res

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.maxOnes(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def maxOnes(self, a, n):
		s = 0
		m = 0
		t = 0
		h = [0] * 2
		h[0] = 1
		h[1] = -1
		for i in range(n):
			t += a[i]
			s += h[a[i]]
			if s > m:
				m = s
			if s < 0:
				s = 0
		return t + m

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.maxOnes(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def maxOnes(self, nums, n):
		if nums.count(1) == n:
			return sum(nums)
		left = 0
		count = 0
		maxCount = float('-inf')
		for i in range(n):
			if nums[i] == 1:
				count -= 1
			else:
				count += 1
			if count > maxCount:
				maxCount = count
				l = left
				r = i
			if count < 0:
				count = 0
				left = i + 1
		for i in range(l, r + 1):
			if nums[i] == 1:
				nums[i] = 0
			else:
				nums[i] = 1
		return sum(nums)

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.maxOnes(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def maxOnes(self, a, n):
		if not a:
			return 0
		num_of_ones = a.count(1)
		if not 0 in a:
			return num_of_ones
		first_index = a.index(0)
		a[first_index] = 1
		for i in range(first_index + 1, len(a)):
			if a[i] == 0:
				a[i] = max(a[i - 1] + 1, 1)
			else:
				a[i] = a[i - 1] - 1
		return max(a) + num_of_ones

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.maxOnes(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def maxOnes(self, arr, n):
		orig_one_count = 0
		max_diff = 0
		curr_max = 0
		for i in range(n):
			if arr[i] == 1:
				orig_one_count += 1
			val = 1 if arr[i] == 0 else -1
			curr_max = max(val, curr_max + val)
			max_diff = max(max_diff, curr_max)
		max_diff = max(0, max_diff)
		return orig_one_count + max_diff


class Solution:

	def maxOnes(self, a, n):
		count_1 = 0
		count_0 = 0
		sum1 = 0
		max_sum = 0
		for i in range(n):
			if a[i] == 1:
				count_1 += 1
			else:
				count_0 += 1
			if a[i] == 1:
				a[i] = -1
			else:
				a[i] = 1
			sum1 = sum1 + a[i]
			max_sum = max(max_sum, sum1)
			if sum1 < 0:
				sum1 = 0
		return max_sum + count_1


class Solution:

	def maxOnes(self, arr, n):
		curr = 0
		maxi = 0
		for i in range(n):
			if arr[i] == 0:
				curr += 1
			else:
				if curr > maxi:
					maxi = curr
				curr -= 1
				if curr < 0:
					curr = 0
		if curr > maxi:
			maxi = curr
		ans = arr.count(1) + maxi
		return ans


class Solution:

	def maxOnes(self, a, n):
		temp = a.copy()
		if sum(temp) == n:
			return n
		for i in range(n):
			if a[i] == 0:
				a[i] = -1
		curr_mini = a[0]
		glb_mini = a[0]
		for i in range(1, n):
			curr_mini = min(a[i], a[i] + curr_mini)
			if curr_mini < glb_mini:
				glb_mini = curr_mini
		return sum(temp) + abs(glb_mini)


class Solution:

	def maxOnes(self, a, n):
		ones = 0
		score = 0
		maxscore = 0
		for i in range(n):
			if a[i] == 1:
				ones += 1
			if a[i] == 1:
				score -= 1
			else:
				score += 1
			maxscore = max(score, maxscore)
			if score < 0:
				score = 0
		return ones + maxscore


class Solution:

	def maxOnes(self, a, n):
		h = [1, -1]
		total = 0
		s = 0
		maxsum = 0
		for i in range(n):
			total += a[i]
			s += h[a[i]]
			maxsum = max(maxsum, s)
			if s < 0:
				s = 0
		return total + maxsum


class Solution:

	def maxOnes(self, a, n):
		cnt = 0
		for i in range(n):
			if a[i] == 0:
				a[i] = 1
			else:
				cnt += 1
				a[i] = -1
		curr = a[0]
		maxx = a[0]
		for i in range(1, n):
			curr = max(a[i], curr + a[i])
			maxx = max(curr, maxx)
		ans = max(cnt, cnt + maxx)
		return ans


class Solution:

	def maxOnes(self, a, n):
		(s, m, cur) = (0, -float('inf'), 0)
		for i in range(n):
			s += a[i]
			cur += 1 if a[i] == 0 else -1
			m = max(m, cur)
			if cur < 0:
				cur = 0
		m = max(0, m)
		return m + s


class Solution:

	def maxOnes(self, a, n):
		sum = 0
		maxZeros = 0
		maxOnes = 0
		ones = 0
		totalOnes = 0
		for i in range(0, n):
			t = 0
			if a[i] == 0:
				t = 1
			else:
				t = -1
				totalOnes += 1
			sum = max(sum + t, t)
			if sum <= 0:
				ones = 0
			elif sum > 0:
				ones += 1
			if maxZeros < sum:
				maxZeros = sum
				maxOnes = ones
		return totalOnes - maxOnes + maxZeros + maxOnes


class Solution:

	def maxOnes(self, a, n):
		maxsum = 0
		ones = 0
		total = 0
		for i in range(n):
			if a[i] == 1:
				ones += 1
			value = -1 if a[i] == 1 else 1
			total = total + value
			maxsum = max(total, maxsum)
			if total < 0:
				total = 0
		return maxsum + ones


class Solution:

	def maxOnes(self, a, n):
		ones = 0
		summ = 0
		maxx = 0
		for i in range(n):
			if a[i] == 1:
				ones += 1
			value = -1 if a[i] == 1 else 1
			summ += value
			maxx = max(summ, maxx)
			if summ < 0:
				summ = 0
		return maxx + ones


class Solution:

	def maxOnes(self, a, n):
		count = 0
		for i in range(0, n):
			if a[i] == 1:
				count += 1
				a[i] = -1
			elif a[i] == 0:
				a[i] = 1
		sums = 0
		sum_so_far = 0
		for i in range(0, n):
			sums = sums + a[i]
			if sum_so_far < sums:
				sum_so_far = sums
			if sums < 0:
				sums = 0
		count = count + sum_so_far
		return count


class Solution:

	def maxOnes(self, a, n):
		arr = [0 for i in range(n)]
		count = 0
		for i in range(n):
			if a[i] == 0:
				arr[i] = 1
			else:
				arr[i] = -1
				count += 1
		(curr, maximum) = (arr[0], arr[0])
		for i in range(1, n):
			curr = max(arr[i], curr + arr[i])
			maximum = max(maximum, curr)
		maximum = max(0, maximum)
		return maximum + count


class Solution:

	def maxOnes(self, a, n):
		totalones = 0
		csum = 0
		maxsum = 0
		for i in range(len(a)):
			if a[i] == 1:
				a[i] = -1
				totalones += 1
			else:
				a[i] = 1
			csum = max(a[i], csum + a[i])
			maxsum = max(csum, maxsum)
		return totalones + maxsum


class Solution:

	def maxOnes(self, a, n):
		nums = []
		count_1 = 0
		count_0 = 0
		for i in range(len(a)):
			if a[i] == 1:
				count_1 += 1
				if count_0 != 0:
					nums.append(count_0)
				if i == n - 1:
					nums.append(-1 * count_1)
				count_0 = 0
			elif a[i] == 0:
				count_0 += 1
				if count_1 != 0:
					nums.append(-1 * count_1)
				if i == n - 1:
					nums.append(count_0)
				count_1 = 0
		n_sum = 0
		for k in nums:
			if k < 0:
				n_sum += k
		rn_sum = 0
		s = 0
		max_s = float('-inf')
		for j in nums:
			s = s + j
			if j < 0:
				rn_sum += j
			if s > max_s:
				max_s = s
				max_rn_sum = rn_sum
			if s <= 0:
				s = 0
				rn_sum = 0
		if max_s > 0:
			ans = max_s - max_rn_sum - (n_sum - max_rn_sum)
		else:
			return -1 * max_s
		return ans


class Solution:

	def maxOnes(self, a, n):
		s = sum(a)
		b = []
		for i in a:
			if i == 1:
				b.append(0)
			else:
				b.append(1)
		d = []
		for i in range(n):
			d.append(b[i] - a[i])
		x = 0
		max_sum = float('-inf')
		for i in d:
			x += i
			if x > max_sum:
				max_sum = x
			if x < 0:
				x = 0
		return max(0, max_sum) + s


class Solution:

	def maxOnes(self, arr, n):
		(count_0, count_1, maxCount) = (0, 0, 0)
		for i in range(n):
			temp = 0
			if arr[i] == 0:
				temp = 1
			else:
				temp = -1
				count_1 += 1
			count_0 = max(0, count_0 + temp)
			maxCount = max(count_0, maxCount)
		return maxCount + count_1


class Solution:

	def maxOnes(self, a, n):
		initialOnes = sum(a)
		runningDiff = 0
		bestDiff = 0
		for i in range(len(a)):
			currEle = a[i]
			if currEle == 1:
				runningDiff -= 1
				continue
			elif runningDiff < 0:
				runningDiff = 1
			else:
				runningDiff += 1
			bestDiff = max(bestDiff, runningDiff)
		return initialOnes + bestDiff


class Solution:

	def maxOnes(self, a, n):
		(curr_sum, max_sum) = (0, 0)
		org_one = 0
		left = right = 0
		for i in range(n):
			if a[i] == 0:
				val = 1
			else:
				org_one += 1
				val = -1
			curr_sum = curr_sum + val
			if curr_sum > max_sum:
				max_sum = curr_sum
				right = i
			if curr_sum < 0:
				curr_sum = 0
				left = i + 1
		return max_sum + org_one


class Solution:

	def maxOnes(self, a, n):
		max_count = 0
		max_s = -1
		max_end = -1
		max_negative = 0
		count = 0
		neative_count = 0
		tmp_i = -1
		tmp_j = -1
		for i in range(n):
			if a[i] == 0:
				if count == 0:
					tmp_i = i
					tmp_j = i
				else:
					tmp_j += 1
				count += 1
			else:
				if count > 0:
					neative_count += 1
					tmp_j += 1
				if count == neative_count:
					count = 0
					neative_count = 0
			if count - neative_count > max_count - max_negative:
				max_count = count
				max_negative = neative_count
				max_s = tmp_i
				max_end = tmp_j
		final_count = 0
		for i in range(n):
			if a[i] == 1 and (max_count == 0 or (i < max_s or i > max_end)):
				final_count += 1
		return final_count + max_count


class Solution:

	def maxOnes(self, a, n):
		ori_one_c = 0
		max_sum = 0
		temp_sum = 0
		for i in range(n):
			if a[i] == 1:
				ori_one_c += 1
			if a[i] == 1:
				temp_sum -= 1
			else:
				temp_sum += 1
			if temp_sum < 0:
				temp_sum = 0
			max_sum = max(temp_sum, max_sum)
		return max_sum + ori_one_c


class Solution:

	def go_and_find(self, a, n, i):
		while i < n and a[i] == 1:
			i += 1
		return i - 1

	def maxOnes(self, a, n):
		ori_one_c = 0
		max_sum = 0
		temp_sum = 0
		for i in range(n):
			if a[i] == 1:
				ori_one_c += 1
			if a[i] == 1:
				temp_sum -= 1
			else:
				temp_sum += 1
			if temp_sum < 0:
				temp_sum = 0
			max_sum = max(temp_sum, max_sum)
		return max_sum + ori_one_c

	def maxOnes1(self, a, n):
		start = 0
		max_l = float('-inf')
		i = 0
		while i < n:
			if a[i] == 0:
				while i < n and a[i] == 0:
					i += 1
				temp = i - start
				start = i
				while i < n and a[i] == 1:
					i += 1
				temp += i - start
				if max_l < temp:
					max_l = temp
			else:
				i += 1
		return max_l


import sys

class Solution:

	def maxOnes(self, a, n):
		for k in range(n):
			if a[k] != 1:
				break
			if k == n - 1:
				return n
		l = 0
		r = 0
		currCount = 0
		maxCount = -sys.maxsize
		count1 = 0
		count0 = 0
		i = 0
		j = 0
		while j < n:
			if a[j] == 1:
				count1 += 1
			else:
				count0 += 1
			currCount = count0 - count1
			if currCount > maxCount:
				l = i
				r = j
				maxCount = currCount
			if currCount < 0:
				i = j + 1
				count1 = 0
				count0 = 0
				currCount = 0
			j += 1
		ans = 0
		for i in range(n):
			if i >= l and i <= r:
				if a[i] == 1:
					a[i] = 0
				else:
					a[i] = 1
			if a[i] == 1:
				ans += 1
		return ans


class Solution:

	def maxOnes(self, a, n):
		m = 0
		c = 0
		for i in a:
			k = -1 if i == 1 else 1
			c = c + k
			m = max(m, c)
			if c < 0:
				c = 0
		return m + a.count(1)


class Solution:

	def maxOnes(self, arr, n):
		mxcnt = 0
		sm = 0
		cnt1 = 0
		for i in range(n):
			if arr[i] == 0:
				tmp = 1
			else:
				tmp = -1
				cnt1 += 1
			sm = max(0, sm + tmp)
			mxcnt = max(mxcnt, sm)
		return mxcnt + cnt1


class Solution:

	def maxOnes(self, a, n):
		count1 = 0
		maxsum = 0
		currsum = 0
		for i in a:
			if i == 1:
				count1 += 1
			if i == 1:
				val = -1
			else:
				val = 1
			currsum += val
			if currsum > maxsum:
				maxsum = currsum
			elif currsum < 0:
				currsum = 0
		return count1 + maxsum


import sys

class Solution:

	def maxOnes(self, arr, n):
		check = 0
		for i in range(n):
			if arr[i] == 0:
				check += 1
		if check == 0:
			return n
		sm = 0
		maxm = -1 * sys.maxsize
		lr = 0
		for i in range(n):
			if arr[i] > 0:
				sm -= arr[i]
			else:
				sm += 1
			if sm > maxm:
				maxm = sm
				right = i
				left = lr
			if sm <= 0:
				sm = 0
				lr = i + 1
		ans = 0
		for i in range(left, right + 1):
			if arr[i] == 0:
				ans += 1
		for i in range(0, left):
			if arr[i] == 1:
				ans += 1
		for i in range(right + 1, n):
			if arr[i] == 1:
				ans += 1
		return ans


class Solution:

	def maxOnes(self, a, n):
		st = None
		(st_max, end_max) = (None, None)
		end = None
		s_max = 0
		s = 0
		for i in range(len(a)):
			if a[i] == 0:
				s -= 1
				if s == -1:
					st = i
				end = i
				if s < s_max:
					s_max = s
					st_max = st
					end_max = i
			elif s < 0:
				s += 1
		if st_max is None:
			zer = 0
			for i in a:
				if i:
					zer += 1
		else:
			zer = 0
			for i in a[:st_max]:
				if i:
					zer += 1
			for i in a[end_max + 1:]:
				if i:
					zer += 1
			for i in a[st_max:end_max + 1]:
				if not i:
					zer += 1
		return zer


class Solution:

	def maxOnes(self, a, n):
		cur_val = max_val = 0
		num_of_1s = 0
		for i in a:
			if i == 0:
				cur_val += 1
			else:
				num_of_1s += 1
				cur_val -= 1
			if cur_val < 0:
				cur_val = 0
			max_val = max(cur_val, max_val)
		return max_val + num_of_1s


class Solution:

	def maxOnes(self, a, n):
		flipped_array = [-1 if x == 1 else 1 for x in a]
		(result, start, end) = self.max_subarray_sum(flipped_array, n)
		if result != -1:
			for i in range(start, end + 1):
				a[i] = 1 - a[i]
		return sum(a)

	def max_subarray_sum(self, a, n):
		max_so_far = a[0]
		max_ending_here = 0
		(start, start_o, end) = (0, 0, 0)
		for i in range(n):
			max_ending_here = max_ending_here + a[i]
			if max_ending_here < 0:
				max_ending_here = 0
				start = i + 1
			elif max_so_far < max_ending_here:
				max_so_far = max_ending_here
				end = i
				start_o = start
		return (max_so_far, start_o, end)


class Solution:

	def maxOnes(self, a, n):
		count = 0
		for i in range(n):
			if a[i] == 0:
				a[i] = 1
			else:
				count += 1
				a[i] = -1
		max_so_far = a[0]
		s = a[0]
		for i in range(1, n):
			s = max(a[i], s + a[i])
			max_so_far = max(max_so_far, s)
		max_so_far = max(0, max_so_far)
		return count + max_so_far


class Solution:

	def maxOnes(self, A, n):
		(a, b) = (0, 0)
		c = 0
		for i in A:
			if i == 1:
				c += 1
				a += -1
			else:
				a += 1
			b = max(a, b)
			if a < 0:
				a = 0
		return b + c


class Solution:

	def maxOnes(self, a, n):
		cont1 = a.count(1)
		diff = 0
		cont_max = 0
		for i in a:
			if i == 1:
				diff -= 1
				if diff < 0:
					diff = 0
			else:
				diff += 1
			cont_max = max(cont_max, diff)
		return cont1 + cont_max


class Solution:

	def maxOnes(self, arr, n):

		def max0s1s(lst, n):
			totalCount = 0
			Count = 0
			ones = 0
			zeroes = 0
			(a, na) = (None, None)
			(b, nb) = (None, None)
			for i in range(n):
				if lst[i] == 1:
					ones += 1
				else:
					zeroes += 1
				count = zeroes - ones
				if count >= totalCount:
					totalCount = count
					if a == None:
						a = i
					b = i
					if na == None or b - a > nb - na:
						nb = b
						na = a
				if count < 0:
					count = 0
					s = 0
					a = None
					b = None
					(zeroes, ones) = (0, 0)
			return totalCount
		count = max0s1s(arr, n)
		return arr.count(1) + count