Given binary string s consisting of 0s and 1s only. You are allowed to do exactly one move that is you have to choose two indices i and j (1 ≤ i ≤ j ≤ |str| where |str| is string length) and toggle all the characters at position k where i ≤ k ≤ j. Toggling means changing 0 to 1 and 1 to 0. The task is to count the maximum possible number of 1's after exactly one move.
Example 1:
Input: s = "1010"
Output: 3
Explanation: You can make move on [2, 2]
or [2, 4]
Example 2:
Input: s = "0000"
Output: 4
Explanation: Make move on [1, 4]
Your Task:  
You don't need to read input or print anything. Complete the function maxOnes() which takes s as an input parameter and returns the maximum number of 1's count.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3
class Solution:
	def maxOnes(self, s):
		# code here

Solutions:
class Solution:

	def maxOnes(self, s):
		mdif = -1
		cdif = -1
		oone = 0
		for i in range(len(s)):
			if s[i] == '1':
				oone += 1
			val = 1 if s[i] == '0' else -1
			cdif = max(val, cdif + val)
			mdif = max(cdif, mdif)
		return oone + mdif


class Solution:

	def maxOnes(self, s):
		s = list(s)
		summ = 0
		st = 0
		e = 0
		mx = float('inf')
		e1 = 0
		e2 = 0
		for i in range(len(s)):
			if s[i] == '1':
				summ += 1
			else:
				summ -= 1
			if summ >= 0:
				summ = 0
				st = i + 1
				e = i + 1
			elif summ < mx:
				mx = summ
				e1 = st
				e2 = i
		count = 0
		for i in range(len(s)):
			if i >= e1 and i <= e2:
				if s[i] == '0':
					s[i] = '1'
				else:
					s[i] = '0'
			if s[i] == '1':
				count += 1
		return count


class Solution:

	def maxOnes(self, s):
		if '0' not in s:
			return len(s) - 1
		count = 0
		maxi = 0
		diff = 0
		for item in s:
			count += item == '1'
			count -= item == '0'
			maxi = max(maxi, count)
			diff = max(diff, maxi - count)
		return s.count('1') + diff


class Solution:

	def maxOnes(self, s):
		cur = 0
		res = []
		count = 0
		for i in s:
			if i == '0':
				res.append(1)
			else:
				res.append(-1)
				count += 1
		n = len(s)
		start = 0
		ans = res[0]
		for i in range(n):
			cur = max(res[i], res[i] + cur)
			ans = max(ans, cur)
		return count + ans


class Solution:

	def maxOnes(self, s):
		x = 0
		n = len(s)
		count = 0
		add = [0] * n
		for i in range(len(s)):
			if s[i] == '1':
				x -= 1
				count += 1
			else:
				x += 1
			add[i] = x
		m1 = len(s) + 1
		m2 = -1 * (len(s) + 1)
		mini = [m1] * n
		maxi = [m2] * n
		mini[0] = add[0]
		if s[0] == '0':
			mini[0] = 0
		maxi[n - 1] = add[n - 1]
		for i in range(1, n):
			mini[i] = min(mini[i - 1], add[i])
		for i in reversed(range(n - 1)):
			maxi[i] = max(add[i], maxi[i + 1])
		ans = maxi[0] - mini[0]
		for i in range(n):
			ans = max(ans, maxi[i] - mini[i])
		if ans == 0:
			return count - 1
		return count + ans