Maximize sum of given array by rearranging array such that the difference between adjacent elements is atmost 1 | 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
def maxSum ( a , n ) : NEW_LINE INDENT count = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT count [ min ( a [ i ] , n ) ] += 1 NEW_LINE DEDENT size = 0 NEW_LINE ans = 0 NEW_LINE for k in range ( 1 , n + 1 ) : NEW_LINE INDENT while ( count [ k ] > 0 and size < k ) : NEW_LINE INDENT size += 1 NEW_LINE ans += size NEW_LINE count [ k ] -= 1 NEW_LINE DEDENT ans += k * count [ k ] NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 3 , 5 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE print ( maxSum ( arr , n ) ) NEW_LINE DEDENT