http://www.iarcs.org.in/inoi/2014/zco2014/zco2014-2b.php

How to tackle such problems…

Is there any way through which we can submit the problem?

@bharatt- No you cannot submit it anywhere.

@kshitijkmr10- I have a DP solution(which I am pretty sure is correct) which I can discuss with you if you want to.

@kshitijkmr10 I told you my dp solution but havent been able to convince you. So I would like @roxtar123 or any other student answer this before telling my DP solution.

So basically we can pick atmost 2 consecutive elements from the array.

Let the input be in array x.

Let dp[i] denote the maximum sum we can obtain till x[i] by choosing atmost 2 consecutive elements.

Trivial Cases-

dp[0]=0;

dp[1]=x[1];

dp[2]=x[1]+x[2];

Now we try filling dp array from i=3 to n.

We have 3 options-

- We take max sum till x[i-1]. Here we cant take x[i] as dp[i-1] has sum till x[i-1].
- Take max sum till x[i-2] and add x[i].
- Take max sum till x[i-3] and add x[i] as well as x[i-1].

Now we fill dp[i] with the maximum of these 3 possible ways.

So our answer will be in dp[n].