Maximize the sum of selected numbers from an array to make it empty | CPP program to Maximize the sum of selected numbers by deleting three consecutive numbers . ; function to maximize the sum of selected numbers ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximizeSum ( int arr [ ] , int n ) { int mx = -1 ; for ( int i = 0 ; i < n ; i ++ ) { mx = max ( mx , arr [ i ] ) ; } int freq [ mx + 1 ] ; memset ( freq , 0 , sizeof ( freq ) ) ; for ( int i = 0 ; i < n ; i ++ ) { freq [ arr [ i ] ] ++ ; } int ans = 0 , i = mx ; while ( i > 0 ) { if ( freq [ i ] > 0 ) { ans += i ; freq [ i - 1 ] -- ; freq [ i ] -- ; } else { i -- ; } } return ans ; } int main ( ) { int a [ ] = { 1 , 2 , 3 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << maximizeSum ( a , n ) ; return 0 ; }