I GOT AC USING TOP DOWN
THIS IS THE SOLUTION THAT I PICKED UP FROM THE INTERNET , HERE BOTTOM UP IS USED.
WHY IS IT CORRECT ITS GOING FROM RIGHT TO LEFT
THE QUESTION SAYS TO GO FROM LEFT TO RIGHT?
int main() {
int t,n,i,j;
scanf("%d",&t);
while(t–)
{
scanf("%d",&n);
LL val[n+8],dp[n+8];
for(i=0;i<n;++i)
scanf("%lld",&val[i]);
/*Initialising all dp[] array with 0
Also, we make extra 7 places 0 in the
*/
memset(dp,0,sizeof(dp));
memset(val+n,0,sizeof(LL)*7);
for(i=n-1;i>=0;--i)
{
/*Case when we take only 1 toy*/
dp[i]=val[i]+dp[i+2];
/*To check profit if we take 2 toys*/
if(i+1<n)
dp[i]=max(dp[i],val[i]+val[i+1]+dp[i+4]);
/*To check for profit if we take 3 toys*/
if(i+2<n)
dp[i]=max(dp[i],val[i]+val[i+1]+val[i+2]+dp[i+6]);
}
printf("%lld\n",dp[0]);
}
return 0;
}