Tell me the apprach please :\

#1

tell me the apprach please :\

#2

Hello @Muskan-Gupta-598128740703036,

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

cool !! , i was almost there , but problem was in forming the recurrence relation