Author: SQU_Test
DIFFICULTY:
Easy
PREREQUISITES:
Basic observations, subsequence of maximal sum
PROBLEM:
Ayoub got bored, so he invented a game to be played on paper.
He writes n integers a_1, a_2, ..., a_n. Each of those integers can be either 0 or 1. He is allowed to do exactly one move: he chooses two indices i and j (1 ≤ i ≤ j ≤ n) and flips all values a_k for which their positions are in range [i, j] (that is i ≤ k ≤ j). Flip the value of x means to apply operation x = 1 - x.
The goal of the game is that after exactly one move to obtain the maximum number of ones. Write a program to solve the little game of Ayoub.
EXPLANATION:
-
O(N^3) Solution: The first thing to observe is that constrains are small enough to allow a brute force algorithm. Using brute force, you can calculate for each possible single move the number of 1s resulting after applying it and take maximum. To consider each move, you can just generate with 2 FOR loops all indices i, j such as i ≤ j. So far we have O(N^2) complexity. Suppose you have now 2 fixed vaIues i and j. You need to calculate variable count (initially 0) representing the number of ones if you do the move. To do this, you choose another index k to go in a[] array (taking O(N) time, making the total of O(N^3) complexity). We have two cases: either k is in range [i, j] (this means i ≤ k and k ≤ j) or not (if that condition is not met). If it’s in range, then it gets flipped, so we add to count variable 1 – a[k] (observe that it makes 0 to 1 and 1 to 0). If it’s not in range, we simply add to count variable a[k]. The answer is maximum of all count obtained.
-
O(N) Solution: To achieve this complexity, we need to make an observation. Suppose you flip an interval (it does not matter what interval, it can be any interval). Also suppose that ones is the number of ones before flipping it. What happens? Every time you flip a 0 value, ones increases by 1 (you get a new 1 value). Every time you flip a 1 value, ones decreases by 1 (you loose a 1 value). What would be the “gain” from a flip? You can consider winning “+1” when you get a 0 value and “-1” when you get a 1 value. The “gain” would be simply a sum of +1 and -1. This gives us idea to make another vector B[]. B[i] is 1 if A[i] is 0 and B[i] is -1 if A[i] is 1. We want to maximize ones + gain_after_one_move sum. As ones is constant, you want to maximize gain_after_one_move. In other words, you want to find a subsequence in B[] which gives the maximal sum. If you flip it, you get maximal number of 1s too. This can be founded trivially in O(N^2). How to get O(N)? A relative experienced programmer in dynamic programming will immediately recognize it as a classical problem “subsequence of maximal sum”.
TIME COMPLEXITY:
Time complexity of the first method is O(N^3) while the complexity of the second method is O(N).
SOLUTIONS:
Setter’s Solution – Second Method O(N)
n = int(input())
a = list(map(int,input().split()) )
ones = sum(a)
tot=0
ans = -1
gain = 0
for i in range(len(a)):
if a[i] == 0:
gain += 1
else:
if gain > 0:
gain -= 1
ans = max(ans , gain)
if ones == n:
print(n-1)
else:
print(ones + ans)