'''
Bob likes to play his game on paper. He writes n integers a1, a2, ..., an. Each of those integers can be either 0 or 1. He's allowed to 
do exactly one move: he chooses two indices i and j (1 ≤ i ≤ j ≤ n) and flips all values ak for which their positions are in range [i, j]
(that is i ≤ k ≤ j). Flip the value of ak means to apply operation ak = 1 - ak.

The goal of the game is that after exactly one move to obtain the maximum number of ones.

Given a list of 0 or 1. Return the maximal number of 1s that can be obtained after exactly one move.

Example 1
Input:
[1, 0, 0, 0, 1, 0, 0, 0]
Output:
7
'''

from typing import List

class Solution(object):
    def solve(self, l:List[int]) -> int:
        current_ones = sum(l)
        max_ones = 0
        for i in range(len(l)):
            for j in range(i, len(l)):
                flipped = l[i:j+1] # Flipping the segment from i to j
                if flipped.count(1) == len(flipped):  # If all are 1
                    new_ones = current_ones - len(flipped) # Flipping all 1s to 0s
                new_ones = current_ones - sum(flipped) + len(flipped) - sum(flipped) # Flipping 0s to 1s and 1s to 0s
                max_ones = max(max_ones, new_ones)   
        return max_ones

s = Solution()
print(s.solve([1, 0, 0, 0, 1, 0, 0, 0]))  # Output: 7
print(s.solve([1, 1, 1, 1, 1, 1, 1, 1]))  # Output: 8
print(s.solve([0, 0, 0, 0, 0, 0, 0, 0]))  # Output: 8

'''
    def solve_optimized(self, l: List[int]) -> int:
        n = len(l)
        current_ones = sum(l)
        max_diff = float('-inf')
        current_diff = 0
        
        for i in range(n):
            if l[i] == 1:
                current_diff -= 1
            else:
                current_diff += 1
            
            if current_diff < 0:
                current_diff = 0
            
            max_diff = max(max_diff, current_diff)
        
        return current_ones + max_diff if max_diff != float('-inf') else current_ones
        
'''