ZCO 2014 (last year) problem


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-

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].