Maximum sum subsequence with values differing by at least 2 | Python3 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 code
from collections import defaultdict NEW_LINE def get_max_sum ( arr , n ) : NEW_LINE INDENT freq = defaultdict ( lambda : 0 ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT freq [ arr [ i ] ] += 1 NEW_LINE DEDENT dp = [ 0 ] * 100001 NEW_LINE dp [ 0 ] = 0 NEW_LINE dp [ 1 ] = freq [ 0 ] NEW_LINE for i in range ( 2 , 100000 + 1 ) : NEW_LINE INDENT dp [ i ] = max ( dp [ i - 1 ] , dp [ i - 2 ] + i * freq [ i ] ) NEW_LINE DEDENT return dp [ 100000 ] NEW_LINE DEDENT N = 3 NEW_LINE arr = [ 2 , 2 , 3 ] NEW_LINE print ( get_max_sum ( arr , N ) ) NEW_LINE