Issue with question

#1

Can someone explain me the question with the explanation of some test cases.

#2

Hello @Bong_Beast go through this:
when you took an element arr[i] from array, all the elements in the array with a value of either arr[i]+1 or arr[i]-1 if exists, will be deleted…(arr[i] will also be deleted) and your answer will only get arr[i].
say for eg. the array is 7 2 1 8 3 3 6 6…

  1. now if you decide to first pick 8, then all the elements with value 7 or 9, if exists, will be deleted. in array 7 exists, so all 7 entries will be deleted and your array becomes 2 1 3 3 6 6…
    and your answer will be 8 only at this point in time.
  2. next pick up 6, then all entries with value 5 or 7 will be deleted… but we don’t have 5 or 7.
    ans = 8+6=14 and array is 2 1 3 3 6
  3. again pick 6, ans = 20, array: 2 1 3 3
  4. same way you can pick both 3, ans = 26, array: 1 (since 2 will be deleted)
  5. pick 1, ans = 27

approach to solve:
this can be solved using 1D dynamic programming…
step1: take an array of size 100001 (max element value possible+1)
step2: this is your frequency array, store elements frequency in this array, elements are indices of the array.
for eg. if array has 6 6 6, then arr[6] = 3
step3: now create 1D dp array of size 100001, with dp[0] = 0 and dp[1] = arr[1],
and update it like(either you take ith element with value arr[i]*i, or you wont):
dp[i] = max(dp[i-1], arr[i]*i + dp[i-2]) , i>=2

step4: return dp[100000]

#3

Please check my code and tell where I am going wrong.

#4

@Bong_Beast check this code:
https://ide.codingblocks.com/s/424656
this code is passing all the test cases.
try to submit it again.
Happy Learning!!

#5

Why are we returning 100000 and not dp[n]?

#6

@Bong_Beast as i can seee your saved code we are returning dp[n] only.