Flip bits in array using python

Cleaned up and made Pythonic

arr1 = [1, 0, 0, 1, 0, 0, 1, 0]
arr2 = [1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
arr3 = [0,0,0,1,1,0,1,0,1,1,0,0,1,1,1]


def maximum_ones(arr):
    """
    Returns max possible number of ones after flipping a span of bit array
    """  

    total_one = 0
    net = 0
    maximum = 0
    for bit in arr:
        if bit:
            total_one += 1
            net -= 1
        else:
            net += 1
        maximum = max(maximum, net)
        if net < 0:
            net = 0
    return total_one + maximum

print(maximum_ones(arr1))
print(maximum_ones(arr2))
print(maximum_ones(arr3))

Output:

6
14
11

If we want the L and R indices

Not so sure about this one. It can probably be made cleaner.

arr1 = [1, 0, 0, 1, 0, 0, 1, 0]
arr2_0 = [1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
arr2_1 = [1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
arr2_2 = [1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
arr3 = [0,0,0,1,1,0,1,0,1,1,0,0,1,1,1]


def maximum_ones(arr):
    """
    Returns max possible number of ones after flipping a span of bit array
    and the (L,R) indices (inclusive) of such a flip
    """ 
    total_one = 0
    net = 0
    maximum = 0
    L = R = 0
    started_flipping = False
    for i, bit in enumerate(arr):
        if bit:
            total_one += 1
            net -= 1
        else:
            net += 1
            if not started_flipping:
                started_flipping = True
                L = i
        if net > maximum:
            maximum = net
            R = i
        if net < 0:
            net = 0
            if i < R:
                L = i
    return (total_one + maximum, (L,R))

print(maximum_ones(arr1))
print(maximum_ones(arr2_0))
print(maximum_ones(arr2_1))
print(maximum_ones(arr2_2))
print(maximum_ones(arr3))

Output:

(6, (1, 5))
(14, (1, 16))
(14, (2, 16))
(14, (3, 16))
(11, (0, 2))

First Iteration

Here is what I had originally, if you want to see the evolution of the thought processes. Here, I was essentially transliterating what I came up with on paper.

Essentially, we traverse the array and start flipping bits (ok, not really), keeping track of cumulative flipped zeros and cumulative flipped ones in two separate arrays along with the total flipped ones in an integer counter. If the difference between flipped ones and zeroes at a given index - the "net" - drops below zero, we 'reset' the cumulative counts back at zero at that index (but nothing else). Along the way, we also keep track of the maximum net we've achieved and the index at which that occurs. Thus, the total is simply the total 1's we've seen, plus the net at the maximum index.

arr = [1, 0, 0, 1, 0, 0, 1, 0]
total_one = 0
one_flip =  [0 for _ in range(len(arr))]
zero_flip = [0 for _ in range(len(arr))]

# deal with first element of array
if arr[0]:
    total_one += 1
else:
    zero_flip[0] = 1

maximum = dict(index=0,value=0) #index, value
i = 1
# now deal with the rest
while i < len(arr):
    # if element is 1 we definitely increment total_one, else, we definitely flip
    if arr[i]:
        total_one += 1
        one_flip[i] = one_flip[i-1] + 1
        zero_flip[i] = zero_flip[i-1]
    else:
        zero_flip[i] = zero_flip[i-1] + 1
        one_flip[i] = one_flip[i-1]

    net = zero_flip[i] - one_flip[i]
    if net > 0:
        if maximum['value'] < net:
            maximum['value'] = net
            maximum['index'] = i
    else: # net == 0, we restart counting our "net"
        one_flip[i] = 0
        zero_flip[i] = 0

    i += 1

maximum_flipped = total_one - one_flip[maximum['index']] + zero_flip[maximum['index']]

Results:

print(total_one, -one_flip[maximum['index']], zero_flip[maximum['index']] )
print(maximum_flipped)
print('________________________________________________')
print(zero_flip, arr, one_flip, sep='\n')
print('maximum index', maximum['index'])

Output:

3 -1 4
6
________________________________________________
[0, 1, 2, 2, 3, 4, 4, 5]
[1, 0, 0, 1, 0, 0, 1, 0]
[0, 0, 0, 1, 1, 1, 2, 2]
maximum index 5

if

arr = [1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]

6 -4 12
14
________________________________________________
[0, 1, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 10, 11, 12, 12]
[1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
[0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 5]
maximum index 16

Finally, if

arr = [0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1]

8 0 3
11
________________________________________________
[1, 2, 3, 3, 3, 4, 4, 5, 5, 0, 1, 2, 2, 0, 0]
[0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1]
[0, 0, 0, 1, 2, 2, 3, 3, 4, 0, 0, 0, 1, 0, 0]
maximum index 2

Great, now tear it apart, people!

Traverse the whole array. Keep a count in the following way:

• Do +1 for every 0 bit encountered.

• Do -1 for every 1.

If this count reaches -ve at any stage, reset it to 0. Keep track of max value of this count. Add this max_count to number of 1's in input array. This will be your answer.

Code:

arr = [1, 0, 0, 1, 0, 0, 1, 0]
# I'm taking your sample case. Take the input the way you want

count,count_max,ones = 0,0,0

for i in arr:
    if i == 1:
        ones += 1
        count -= 1
    if i == 0:
        count += 1
    if count_max < count:
        count_max = count
    if count < 0:
        count = 0

print (ones + count_max)

Small and simple :)