Sherlock and Cost Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
abs(ar[i]-1) is not added to dp[i][0] because dp[i][0] means we are taking ar[i]=1 and dp[i+1][0] means we are taking ar[i+1] as 1 now abs(ar[i]-1) will be abs(1-1) which is 0.so there is no need to add someting which is always going to be zero
Here are two columns '0' and '1'.
'0' column indicates take present ar[i] = 1
while
'1' column indicates take present ar[i] = b[i] i.e. the max possible value .
for dp[i][0] (present value = 1) :
either dp[i-1][0] + abs(1 - 1) as previous value=1 and present value=1
or dp[i-1][1] + abs(1 - ar[i-1]) as previous value=max and present value=1
for dp[i][1] ( present value = max i.e. arr[i] ) :
either dp[i-1][0] + abs(1 - ar[i]) as previous value=1 and present value=max
or dp[i-1][1] + abs(ar[i]- ar[i-1]) as previous value=max and present value=max
Sherlock and Cost
You are viewing a single comment's thread. Return to all comments →
Thank you for clarifying.
So I can just put the whole app in a big loop and do input/output/input/output?
Yup !
Hey can you explain me this pls!
In this statement,dp[i+1][0]=max(dp[i][0],dp[i][1]+abs(ar[i]-1)); why is abs(ar[i]-1) added to dp[i][1] and not to dp[i][0]?
abs(ar[i]-1) is not added to dp[i][0] because dp[i][0] means we are taking ar[i]=1 and dp[i+1][0] means we are taking ar[i+1] as 1 now abs(ar[i]-1) will be abs(1-1) which is 0.so there is no need to add someting which is always going to be zero
thank for your explaning.
Here are two columns '0' and '1'. '0' column indicates take present ar[i] = 1 while '1' column indicates take present ar[i] = b[i] i.e. the max possible value .
for dp[i][0] (present value = 1) :
either dp[i-1][0] + abs(1 - 1) as previous value=1 and present value=1 or dp[i-1][1] + abs(1 - ar[i-1]) as previous value=max and present value=1
for dp[i][1] ( present value = max i.e. arr[i] ) :
either dp[i-1][0] + abs(1 - ar[i]) as previous value=1 and present value=max or dp[i-1][1] + abs(ar[i]- ar[i-1]) as previous value=max and present value=max
therefore, dp[i][0]=max(dp[i-1][0],dp[i-1][1]+abs(ar[i-1]-1));
dp[i][1]=max(dp[i-1][0]+abs(ar[i]-1),dp[i-1][1]+abs(ar[i-1]-ar[i]));
thankyou for the great explanation
thanku...it really helped.
What is the base case for this dp array? Like what should I initialise for dp[0][0] and dp[0][1]?
both with 0 becz we will start adding value when we have atleast two elements.
please explain me again. I still not understand
please explain me the above snippet of the code. I still not