Maximize the sum of selected numbers from an array to make it empty | Java implementation of the approach ; Function to maximise the sum of selected numbers by deleting occurences of Ai - 1 and Ai + 1 ; Number of elements in the array ; Largest element in the array ; An array to count the occurence of each element ; ans to store the result ; Using the above mentioned approach ; if occurence is greater than 0 ; add it to ans ; decrease i - 1 th element by 1 ; decrease ith element by 1 ; decrease i ; Driver code
import java . util . * ; import java . math . * ; class GFG { public static int getMaximumSum ( int arr [ ] ) { int n = arr . length ; int max = - 1 ; for ( int i = 0 ; i < n ; i ++ ) { max = Math . max ( max , arr [ i ] ) ; } int [ ] freq = new int [ max + 1 ] ; for ( int i = 0 ; i < n ; i ++ ) { freq [ arr [ i ] ] ++ ; } int ans = 0 , i = max ; while ( i > 0 ) { if ( freq [ i ] > 0 ) { ans += i ; freq [ i - 1 ] -- ; freq [ i ] -- ; } else { i -- ; } } return ans ; } public static void main ( String [ ] args ) { int [ ] a = { 1 , 2 , 3 } ; System . out . println ( getMaximumSum ( a ) ) ; } }