Rearrange an array to maximize sum of Bitwise AND of same | Function to implement recursive DP ; If i is equal to N ; If dp [ i ] [ mask ] is not equal to - 1 ; Iterate over the array B [ ] ; If current element is not yet selected ; Update dp [ i ] [ mask ] ; Return dp [ i ] [ mask ] ; Function to obtain maximum sum of Bitwise AND of same - indexed elements from the arrays A [ ] and B [ ] ; Stores all dp - states ; Returns the maximum value returned by the function maximizeAnd ( ) ; Driver Code
def maximizeAnd ( i , mask , A , B , N , dp ) : NEW_LINE INDENT if ( i == N ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ i ] [ mask ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ mask ] NEW_LINE DEDENT for j in range ( N ) : NEW_LINE INDENT if ( ( mask & ( 1 << j ) ) == 0 ) : NEW_LINE INDENT dp [ i ] [ mask ] = max ( dp [ i ] [ mask ] , ( A [ i ] & B [ j ] ) + maximizeAnd ( i + 1 , mask | ( 1 << j ) , A , B , N , dp ) ) NEW_LINE DEDENT DEDENT return dp [ i ] [ mask ] NEW_LINE DEDENT def maximizeAndUtil ( A , B , N ) : NEW_LINE INDENT temp = [ - 1 for i in range ( 1 << N + 1 ) ] NEW_LINE dp = [ temp for i in range ( N ) ] NEW_LINE return maximizeAnd ( 0 , 0 , A , B , N , dp ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 3 , 5 , 7 , 11 ] NEW_LINE B = [ 2 , 6 , 10 , 12 ] NEW_LINE N = len ( A ) NEW_LINE print ( maximizeAndUtil ( A , B , N ) ) NEW_LINE DEDENT