Rearrange an array to maximize sum of Bitwise AND of same | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximizeAnd ( int i , int mask , int * A , int * B , int N , vector < vector < int > > & dp ) { if ( i == N ) return 0 ; if ( dp [ i ] [ mask ] != -1 ) return dp [ i ] [ mask ] ; for ( int j = 0 ; j < N ; ++ j ) { if ( ! ( mask & ( 1 << j ) ) ) { dp [ i ] [ mask ] = max ( dp [ i ] [ mask ] , ( A [ i ] & B [ j ] ) + maximizeAnd ( i + 1 , mask | ( 1 << j ) , A , B , N , dp ) ) ; } } return dp [ i ] [ mask ] ; } int maximizeAndUtil ( int * A , int * B , int N ) { vector < vector < int > > dp ( N , vector < int > ( 1 << N + 1 , -1 ) ) ; return maximizeAnd ( 0 , 0 , A , B , N , dp ) ; } int main ( ) { int A [ ] = { 3 , 5 , 7 , 11 } ; int B [ ] = { 2 , 6 , 10 , 12 } ; int N = sizeof A / sizeof A [ 0 ] ; cout << maximizeAndUtil ( A , B , N ) ; }