Facing issue with logic

#1

So what i understood is we have to find maximum sum in such a way without selecting consecutive 3 elements right?
so for this suppose i define dp[i] to be max of(dp[i-2]+dp[i-1],dp[i]) will be writee? coz either he can choose the ith element or he can choose sum of i-1 + i-2th element?

#2

Hello @pranjalarora98 ,

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 element 
dp[0] = a[0];
//taking first and second element
dp[1] = a[1];

For third element we will have 3 cases :

1- Discarding 3rd element

dp[2] = d[1];

2- Discarding 2nd element :

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

3- Discarding 1st element :

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];
  dp[i] = max(dp[i],dp[i-2]+a[i]);
  dp[i] = max(dp[i],dp[i-3] + a[i-1]+a[i]);

Hope, this would help.

#3

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.