Flip Bits Python

PROGRAM TO MAXIMISE NUMBER OF 0s BY FLIPPING A SUBARRAY







def findMaxZeroCount(arr, n):

     

    # Initialize count of zeros and

    # maximum difference between count

    # of 1s and 0s in a subarray

    orig_zero_count = 0

     

    # Initialize overall max diff

    # for any subarray

    max_diff = 0

     

    # Initialize current diff

    curr_max = 0

     

    for i in range(n):

         

        # Count of zeros in original

        # array (Not related to

        # Kadane's algorithm)

        if arr[i] == 0:

            orig_zero_count += 1

         

        # Value to be considered for

        # finding maximum sum

        val = 1 if arr[i] == 1 else -1

         

        # Update current max and max_diff

        curr_max = max(val, curr_max + val)

        max_diff = max(max_diff, curr_max)

         

    max_diff = max(0, max_diff)

     

    return orig_zero_count + max_diff

 

# Driver code

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

n = len(arr)

 

print(findMaxZeroCount(arr, n))




OUTPUT:

6

CREDITS: https://www.geeksforgeeks.org/maximize-number-0s-flipping-subarray/