Partition the array in K segments such that bitwise AND of individual segment sum is maximized | CPP program to find maximum possible AND ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool checkpossible ( int mask , int * arr , int * prefix , int n , int k ) { bool dp [ n + 1 ] [ k + 1 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; dp [ 0 ] [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= k ; j ++ ) { for ( int l = i - 1 ; l >= 0 ; -- l ) { if ( dp [ l ] [ j - 1 ] && ( ( ( prefix [ i ] - prefix [ l ] ) & mask ) == mask ) ) { dp [ i ] [ j ] = 1 ; break ; } } } } return dp [ n ] [ k ] ; } int Partition ( int arr [ ] , int n , int k ) { int prefix [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) { prefix [ i ] = prefix [ i - 1 ] + arr [ i ] ; } int LOGS = 20 ; int ans = 0 ; for ( int i = LOGS ; i >= 0 ; -- i ) { if ( checkpossible ( ans | ( 1 << i ) , arr , prefix , n , k ) ) { ans = ans | ( 1 << i ) ; } } return ans ; } int main ( ) { int arr [ ] = { 0 , 1 , 2 , 7 , 10 , 23 , 21 , 6 , 8 , 7 , 3 } , k = 2 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) - 1 ; cout << Partition ( arr , n , k ) ; return 0 ; }