# ZCO 2014 (last year) problem

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.

yeah sure, why not!.. @roxtar123

@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;
dp=x;
dp=x+x;

Now we try filling dp array from i=3 to n.
We have 3 options-

1. We take max sum till x[i-1]. Here we cant take x[i] as dp[i-1] has sum till x[i-1].
2. Take max sum till x[i-2] and add x[i].
3. 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].