Maximum sum subsequence with values differing by at least 2 | C ++ program to find maximum sum subsequence with values differing by at least 2 ; function to find maximum sum subsequence such that two adjacent values elements are not selected ; map to store the frequency of array elements ; make a dp array to store answer upto i th value ; base cases ; iterate for all possible values of arr [ i ] ; return the last value ; Driver function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int get_max_sum ( int arr [ ] , int n ) { unordered_map < int , int > freq ; for ( int i = 0 ; i < n ; i ++ ) { freq [ arr [ i ] ] ++ ; } int dp [ 100001 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; dp [ 0 ] = 0 ; dp [ 1 ] = freq [ 0 ] ; for ( int i = 2 ; i <= 100000 ; i ++ ) { dp [ i ] = max ( dp [ i - 1 ] , dp [ i - 2 ] + i * freq [ i ] ) ; } return dp [ 100000 ] ; } int main ( ) { int N = 3 ; int arr [ ] = { 2 , 2 , 3 } ; cout << get_max_sum ( arr , N ) ; return 0 ; }