Maximize sum of given array by rearranging array such that the difference between adjacent elements is atmost 1 | C ++ program for the above approach ; Function to find maximum possible sum after changing the array elements as per the given constraints ; 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 [ ] ; Size of array ; Function Call
#include <iostream> NEW_LINE using namespace std ; long maxSum ( int a [ ] , int n ) { int count [ n + 1 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) count [ min ( a [ i ] , 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 ; } int main ( ) { int arr [ ] = { 3 , 5 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << ( maxSum ( arr , n ) ) ; return 0 ; }