Maximum set bit sum in array without considering adjacent elements | Java program to maximum set bit sum in array without considering adjacent elements ; Function to count total number of set bits in an integer ; Maximum sum of set bits ; Calculate total number of set bits for every element of the array ; find total set bits for each number and store back into the array ; current max excluding i ; current max including i ; return max of incl and excl ; Driver code
import java . util . * ; import java . lang . * ; import java . io . * ; class GFG { static int bit ( int n ) { int count = 0 ; while ( n > 0 ) { count ++ ; n = n & ( n - 1 ) ; } return count ; } static int maxSumOfBits ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) { arr [ i ] = bit ( arr [ i ] ) ; } int incl = arr [ 0 ] ; int excl = 0 ; int excl_new ; for ( int i = 1 ; i < n ; i ++ ) { excl_new = ( incl > excl ) ? incl : excl ; incl = excl + arr [ i ] ; excl = excl_new ; } return ( ( incl > excl ) ? incl : excl ) ; } public static void main ( String args [ ] ) { int arr [ ] = { 1 , 2 , 4 , 5 , 6 , 7 , 20 , 25 } ; int n = arr . length ; System . out . print ( maxSumOfBits ( arr , n ) ) ; } }