Neighbour Enemy - Please suggest what i am missing in the code

#1

Hi,
Apart from two my all test cases are failing. This is my code https://ide.codingblocks.com/s/248538. Could you please suggest what I am missing.

#2

you have to consider those elements with 0 frequency as well!
example:
2
1 4
answer = 5, but your code gives 4

#3

I have modified the code and update there in above link still few test cases are failing. Could you please suggest what i am missing.

#4

don’t put unnecessary if statements(As it might lead to incorrect judgement!),
DP recurrence is simply:
dp[i] = max(dp[i+1],dp[i]+dp[i+2]) for i from n-1 to 0.

#5

Hello,

Could you please suggest in case of below i/p how the recurrence dp[i] = Math.max(i*freq[i] + dp[i-2] , dp[i-1]) will work.

Ex - 1 4 5 7 9 4

|1 | 4 | 5 | 7 | 9 | 4 |

Freqy Arr

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

| 0 | 1 | 0 | 0 | 2 | 1 | 0 | 1 | 0 | 1 |

dpArr

For i = 0 to 3
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

For i = 4

| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |

dp [4] = max (i * freq[i] + dp[i-2] , dp[i-1])
dp [4] = max (4 * 2 + 1 , 1) => 9

| 0 | 1 | 1 | 1 | 9 | 0 | 0 | 0 | 0 | 0 |

For i = 5

| 0 | 1 | 1 | 1 | 9 | 0 | 0 | 0 | 0 | 0 |

dp [5] = max (i * freq[i] + dp[i-2] , dp[i-1])
dp [4] = max (5 * 1 + 1 , 9) => 9

| 0 | 1 | 1 | 1 | 9 | 9 | 0 | 0 | 0 | 0 |

For i = 6

Also the value of last index will carry forward

 | 0 | 1 | 1 | 1 | 9 | 9 | 9 | 0 | 0 | 0 |

but for i = 7

but for i = 7 here we need value 5 as well but which is not the part of dp[i-1] and 
dp[i-2] , same is the case of i = 9
so in that case how this recurrence will help
#6

don’t put unnecessary if statements(As it might lead to incorrect judgement!),
DP recurrence is simply:
dp[i] = max(dp[i+1],dp[i]+dp[i+2]) for i from n-1 to 0.[quote=“mayankA47, post:4, topic:67109”]
for i from n-1 to 0.
[/quote]

you already have dp[5] = 9, so dp[7] = 16, and similarly dp[9]=25, which is the answer

#7

Its getting bit confusing for me. 5 doesn’t comes in ±1 range of 7 then we are not considering it in dp[7].

#8

in that case answer for (1,4) should be 4 not 5

#9

We ignore 5 not because of 7, but because of 4!!!(as contribution from 4 is 8(2 elements)).

#10

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.