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
' NEW_LINE def checkpossible ( mask , arr , prefix , n , k ) : NEW_LINE ' NEW_LINE INDENT dp = [ [ 0 for i in range ( k + 1 ) ] for i in range ( n + 1 ) ] NEW_LINE dp [ 0 ] [ 0 ] = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , k + 1 ) : NEW_LINE INDENT for l in range ( i - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( dp [ l ] [ j - 1 ] and ( ( ( prefix [ i ] - prefix [ l ] ) & mask ) == mask ) ) : NEW_LINE INDENT dp [ i ] [ j ] = 1 NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT return dp [ n ] [ k ] NEW_LINE DEDENT def Partition ( arr , n , k ) : NEW_LINE INDENT prefix = [ 0 for i in range ( n + 1 ) ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT prefix [ i ] = prefix [ i - 1 ] + arr [ i ] NEW_LINE DEDENT LOGS = 20 NEW_LINE ans = 0 NEW_LINE for i in range ( LOGS , - 1 , - 1 ) : NEW_LINE INDENT if ( checkpossible ( ans | ( 1 << i ) , arr , prefix , n , k ) ) : NEW_LINE INDENT ans = ans | ( 1 << i ) NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT arr = [ 0 , 1 , 2 , 7 , 10 , 23 , 21 , 6 , 8 , 7 , 3 ] NEW_LINE k = 2 NEW_LINE n = len ( arr ) - 1 NEW_LINE print ( Partition ( arr , n , k ) ) NEW_LINE