Can u explain me how is the output 27 i am getting an ans of 24 for worst possible case

#1

explain why is the ans 27

#2

It looks like you misinterpreted the question(question is also a bit misleading)…
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]

please rate and resolve if satisfied.
thanks

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.