I am trying this question from yesterday but still i am unable to figure out the logic for it . Seeing code is not helping me a lot . Please Provide me Detailed Explanation for the same !!
Unable to Understand
@deepak19.engg
In this task we need to maximize the sum of numbers that we took. Let precalc array cnt . cnt [ x ] — number of integers x in array a . Now we can easily calculate the DP:
f ( i ) = max ( f ( i - 1), f ( i - 2) + cnt [ i ]· i ), 2 ≤ i ≤ n ;
f (1) = cnt [1];
f (0) = 0;
The answer is f ( n ).
Asymptotics — O ( n ).
basically if we take a no i so for it
For each value you have 2 options, DP[i] = max( i*freq[i]+DP[i-2] , DP[i-1] )
do you want code for the same logic ?
Please Explain me the thinking behind it … How you came across this relation ??
i thought like this like if i am at a no i starting from start i came to a no i. if i took i ans will be ans of i which is i * freq of i plus ans of i -2 as i-1 is deleted. and other case is if i do not take it so simple ans of prev @deepak19.engg
how it is handling the case of a[i]+1 element to be deleted
its dp we are going to every element and calculating its ans and final ans max of all
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.