59 lines
1.9 KiB
Python
59 lines
1.9 KiB
Python
'''
|
|
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
|
|
|
|
'''
|
|
|