Maximize sum of given array by rearranging array such that the difference between adjacent elements is atmost 1 | Java program for the above approach ; Function to find maximum possible sum after changing the array elements as per the given constraints ; Length of given array ; Stores the frequency of elements in given array ; Update frequency ; stores the previously selected integer ; Stores the maximum possible sum ; Traverse over array count [ ] ; Run loop for each k ; Update ans ; Return maximum possible sum ; Driver Code ; Given array arr [ ] ; Function Call
import java . util . * ; class GFG { static long maxSum ( int [ ] a ) { int n = a . length ; int [ ] count = new int [ n + 1 ] ; for ( int x : a ) count [ Math . min ( x , n ) ] ++ ; int size = 0 ; long ans = 0 ; for ( int k = 1 ; k <= n ; k ++ ) { while ( count [ k ] > 0 && size < k ) { size ++ ; ans += size ; count [ k ] -- ; } ans += k * count [ k ] ; } return ans ; } public static void main ( String [ ] args ) { int [ ] arr = { 3 , 5 , 1 } ; System . out . println ( maxSum ( arr ) ) ; } }