Maximum Sum of Products of two arrays by toggling adjacent bits | Python3 program to find the maximum SoP of two arrays by toggling adjacent bits in the second array ; Function to return Max Sum ; intialParity and finalParity are 0 if total no . of 1 's is even else 1 ; minPositive and maxNegative will store smallest positive and smallest negative integer respectively . ; Count of Initial Parity ; if arr1 [ i ] is positive then add 1 in finalParity to get 1 at arr2 [ i ] ; if both parity are odd or even then return sum ; else add one more 1 or remove 1 ; if minPositive > maxNegative , put 1 at maxNegative and add it to our sum ; else remove minPositive no . ; Driver code
import sys NEW_LINE def maxSum ( arr1 , arr2 , n ) : NEW_LINE INDENT initialParity , finalParity = 0 , 0 NEW_LINE sum = 0 NEW_LINE minPositive = sys . maxsize NEW_LINE maxNegative = - sys . maxsize - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT initialParity += arr2 [ i ] ; NEW_LINE if ( arr1 [ i ] >= 0 ) : NEW_LINE INDENT finalParity += 1 NEW_LINE sum += arr1 [ i ] NEW_LINE minPositive = min ( minPositive , arr1 [ i ] ) NEW_LINE DEDENT else : NEW_LINE INDENT maxNegative = max ( maxNegative , arr1 [ i ] ) NEW_LINE DEDENT DEDENT if ( initialParity % 2 == finalParity % 2 ) : NEW_LINE INDENT return sum NEW_LINE DEDENT else : NEW_LINE INDENT if ( minPositive + maxNegative >= 0 ) : NEW_LINE INDENT return sum + maxNegative NEW_LINE DEDENT else : NEW_LINE INDENT return sum - minPositive NEW_LINE DEDENT DEDENT DEDENT arr1 = [ 2 , - 4 , 5 , 3 ] NEW_LINE arr2 = [ 0 , 1 , 0 , 1 ] NEW_LINE n = len ( arr1 ) NEW_LINE print ( maxSum ( arr1 , arr2 , n ) ) NEW_LINE