IPL DP-1 question

#1

Sir I have implemented and submitted the solution, however I facing problem understanding that how this approach mentioned in editorial makes sure that 3 players in a row would never be selected.

#2

Hello @pangatt4 ,

You can easily go on this problem with 1-D DP Let: dp[i] = sum taking no 3 Consecutive elements till Index i .

Starting with base cases:

//taking only first match
dp[0] = a[0];
//taking first and second match
dp[1] = a[1]+a[0];

Now For third element we will have 3 cases :

1- Discarding 3rd match

dp[2] = d[1];

2- Discarding 2nd match :

dp[2] = dp[0] + a[2]

3- Discarding 1st match :

dp[2] = a[1] + a[2]

so Final Dp[2] will be maximum of these 3:

dp[2] = max( dp[1] , max( dp[0] + a[2] , a[1] + a[2] ) );

We can extend same approach for ith element :

  dp[i] = dp[i-1]; //discard current match 
  dp[i] = max(dp[i],dp[i-2]+a[i]);  //discard previous match i.e i-1
  dp[i] = max(dp[i],dp[i-3] + a[i-1]+a[i]);  //discard  i-2 nd match

Hope, this would help.

1 Like
#3

Okay, that was indeed intuitive approach, thank you.

1 Like
#4

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.