codesignal-dp-maximizesum.py

ip = [5,6,6,4,11]
# ip = [3,4,2]
# ip = [1,2,1,3,2,3]

from collections import Counter

c = Counter(ip)
print("Counter:", c)

s = 0
for key in sorted(list(c.keys()),reverse=True):
    if c[key] == 0:
        continue
    print("Key:", key)
    s += c[key] * key
    print(s)
    if key + 1 in c.keys():
        c[key+1] = 0
        #c.pop(key+1, None)
    if key - 1 in c.keys():
        #c.pop(key-1, None)
        c[key-1] = 0
    
    
#full answer on geeksforgeeks -  and hackerrank - Maximize Sum/Numbers and codeforces Q455A

def maximizeSum(a, n) :
 
    # stores the occurrences of the numbers 
    ans = dict.fromkeys(range(0, n + 1), 0) 
 
    # marks the occurrence of every 
    # number in the sequence 
    for i in range(n) : 
        ans[a[i]] += 1
 
    # maximum in the sequence 
    maximum = max(a) 
 
    # traverse till maximum and apply
    # the recurrence relation 
    for i in range(2, maximum + 1) :
        ans[i] = max(ans[i - 1], 
                     ans[i - 2] + ans[i] * i)
 
    # return the ans stored in the 
    # index of maximum 
    return ans[maximum] 
    
arr = [5,6,6,4,11]
maximizeSum(arr,len(arr))