Alice and bob 1 d dp

#1

can’t this be a solution to this problem
i m thinking greedily and adding those elemnts to my ans for which a[i+1]-a[i] == a[i]-a[i-1]

code link https://ide.codingblocks.com/s/207240

#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 6 7 8 10 6 7 8…
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 6 10 6 8…
and your answer will be 8 only at this point in time.

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]

thanks

1 Like
#3
#4

sir ab answer 0 aa rha

#5

the code you shared looks a completely different code. please recheck it.
thanks

#6

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.

#7

@avinashmallik2017
How can I help you ?

#8

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.