Maximum score of deleting an element from an Array based on given condition | C ++ implementation to find the maximum score of the deleting a element from an array ; Function to find the maximum score of the deleting an element from an array ; Creating a map to keep the frequency of numbers ; Loop to iterate over the elements of the array ; Creating a DP array to keep count of max score at ith element and it will be filled in the bottom Up manner ; Loop to choose the elements of the array to delete from the array ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMaximumScore ( vector < int > a , int n ) { unordered_map < int , int > freq ; for ( int i = 0 ; i < n ; i ++ ) { freq [ a [ i ] ] ++ ; } vector < int > dp ( * max_element ( a . begin ( ) , a . end ( ) ) + 1 , 0 ) ; dp [ 0 ] = 0 ; dp [ 1 ] = freq [ 1 ] ; for ( int i = 2 ; i < dp . size ( ) ; i ++ ) dp [ i ] = max ( dp [ i - 1 ] , dp [ i - 2 ] + freq [ i ] * i ) ; return dp [ dp . size ( ) - 1 ] ; } int main ( ) { int n ; n = 3 ; vector < int > a { 1 , 2 , 3 } ; cout << findMaximumScore ( a , n ) ; return 0 ; }