Partition the array in K segments such that bitwise AND of individual segment sum is maximized | Function to check whether a k segment partition is possible such that bitwise AND is ' mask ' ; dp [ i ] [ j ] stores whether it is possible to partition first i elements into j segments such that all j segments are ' good ' ; Initialising dp ; Filling dp in bottom - up manner ; Finding a cut such that first l elements can be partitioned into j - 1 ' good ' segments and arr [ l + 1 ] + ... + arr [ i ] is a ' good ' segment ; Function to find maximum possible AND ; Array to store prefix sums ; Maximum no of bits in the possible answer ; This will store the final answer ; Constructing answer greedily selecting from the higher most bit ; Checking if array can be partitioned such that the bitwise AND is ans | ( 1 << i ) ; if possible , update the answer ; Return the final answer ; Driver code ; n = 11 , first element is zero to make array 1 based indexing . So , number of elements are 10 ; Function call
function checkpossible ( mask , arr , prefix , n , k ) { let i , j ; let dp = new Array ( n + 1 ) ; for ( i = 0 ; i < n + 1 ; i ++ ) { dp [ i ] = new Array ( k + 1 ) ; for ( j = 0 ; j < k + 1 ; j ++ ) { dp [ i ] [ j ] = false ; } } dp [ 0 ] [ 0 ] = true ; for ( i = 1 ; i <= n ; i ++ ) { for ( j = 1 ; j <= k ; j ++ ) { for ( let l = i - 1 ; l >= 0 ; -- l ) { if ( dp [ l ] [ j - 1 ] && ( ( ( prefix [ i ] - prefix [ l ] ) & mask ) == mask ) ) { dp [ i ] [ j ] = true ; break ; } } } } return dp [ n ] [ k ] ; } function Partition ( arr , n , k ) { let prefix = new Array ( n + 1 ) ; prefix . fill ( 0 ) ; for ( let i = 1 ; i <= n ; i ++ ) { prefix [ i ] = prefix [ i - 1 ] + arr [ i ] ; } let LOGS = 20 ; let ans = 0 ; for ( let i = LOGS ; i >= 0 ; -- i ) { if ( checkpossible ( ans | ( 1 << i ) , arr , prefix , n , k ) ) { ans = ans | ( 1 << i ) ; } } return ans ; } let arr = [ 0 , 1 , 2 , 7 , 10 , 23 , 21 , 6 , 8 , 7 , 3 ] , k = 2 ; let n = arr . length - 1 ; document . write ( Partition ( arr , n , k ) ) ;