Flip Flop Sum (Codeforces 1778A)
Tags: Greedy, implementation

You are given an array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. The integers are either $$$1$$$ or $$$-1$$$. You have to perform the following operation exactly once on the array $$$a$$$:  Choose an index $$$i$$$ ($$$1 \leq i < n$$$) and flip the signs of $$$a_i$$$ and $$$a_{i+1}$$$. Here, flipping the sign means $$$-1$$$ will be $$$1$$$ and $$$1$$$ will be $$$-1$$$. What is the maximum possible value of $$$a_1 + a_2 + \ldots + a_n$$$ after applying the above operation?

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$), the length of the array $$$a$$$.The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i = 1$$$ or $$$a_i = -1$$$).The sum of $$$n$$$ over all cases doesn't exceed $$$10^5$$$.

Output: For each test case, print the maximum possible sum of the array $$$a$$$ you can get in a separate line.

Note: In the first case, we can choose index $$$4$$$ and flip the signs of $$$a_4$$$ and $$$a_5$$$. After this operation, the sum will be $$$-1+1+1+1+1 = 3$$$. We can't make the sum larger than this.In the third case, the only option is to choose the index $$$1$$$.

Sample Inputs:
4
5
-1 1 1 -1 -1
5
1 1 -1 -1 -1
2
1 1
4
1 -1 -1 1

Sample Outputs:
3
3
-2
4

Solution (Python):
t = int(input())
for i in range(t):
    a = int(input())
    n = input()
    x = n.count('1') - n.count('-1') * 2
    if n.find('-1') == -1:
        print(x - 4)
    elif n.find('-1 -1') != -1:
        print(x + 4)
    else:
        print(x)

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    f = False
    for i in range(1, n):
        if l[i] == l[i - 1] == -1:
            l[i] = 1
            l[i - 1] = 1
            f = True
            break
    if not f:
        for i in range(1, n):
            if l[i] != l[i - 1]:
                f = True
                break
    e = 0
    if not f:
        e = -4
    print(sum(l) + e)

Solution (Python):
for i in range(int(input())):
    size = int(input())
    s = input()
    l = list(map(int, s.split()))
    if '-1 -1' in s:
        print(sum(l) + 4)
    elif '-1' in s:
        print(sum(l))
    else:
        print(sum(l) - 4)