Rearrange an array to maximize sum of Bitwise AND of same | Java 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
import java . io . * ; import java . lang . * ; import java . util . * ; public class GFG { static int maximizeAnd ( int i , int mask , int A [ ] , int B [ ] , int N , 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 ) ) == 0 ) { dp [ i ] [ mask ] = Math . max ( dp [ i ] [ mask ] , ( A [ i ] & B [ j ] ) + maximizeAnd ( i + 1 , mask | ( 1 << j ) , A , B , N , dp ) ) ; } } return dp [ i ] [ mask ] ; } static int maximizeAndUtil ( int A [ ] , int B [ ] , int N ) { int dp [ ] [ ] = new int [ N ] [ ( 1 << N ) + 1 ] ; for ( int dd [ ] : dp ) Arrays . fill ( dd , - 1 ) ; return maximizeAnd ( 0 , 0 , A , B , N , dp ) ; } public static void main ( String [ ] args ) { int A [ ] = { 3 , 5 , 7 , 11 } ; int B [ ] = { 2 , 6 , 10 , 12 } ; int N = A . length ; System . out . print ( maximizeAndUtil ( A , B , N ) ) ; } }