**PROBLEM SETTER** -

ZCO 2014

**DIFFICULTY** –

Easy-medium

**PREREQUISITES** –

Dynamic Programming

**PROBLEM IN SHORT** –

We have to select some elements from the array, so that the sum of selected elements is as maximum as possible with respect to constraint that there should not be 3 or more selected consecutive elements.

**KEY OBSERVATIONS** –

We always have two choices while selecting a number which are, that the previous element is selected or not.

**EXPLANATION** –

From key observations, we can build a recurrence. This recurrence can be easily implemented by dynamic programming. dp[i][j] denotes the maximum answer for array [1,i] by selecting i^{th} element where j is 0 if previous element is not selected and 1 if it is. If j is 1, **dp[i][j]** will be simply **( a[i] + dp[i-1][0] )**. We can’t do dp[i-1][1] because it means that we selected 3 elements in total which is not possible. If j is 0, we can select second last or third last element. So it will look like this -

dp[i][0] = a[i] + max( dp[i-2][0] , dp[i-2][1] , dp[i-3][1] ).

The overall recurrence code will look like this –

for(int i = 1;i < n+1;i++) { // for j = 0, dp[i][0] = a[i] + max(max(dp[i-2][0],dp[i-2][1]),dp[i-3][1]); // for j = 1, dp[i][1] = a[i] + dp[i-1][0]; }

The answer to the problem would be maximum of dp[N][1], dp[N][0] and dp[N-1][1], as we have to select at least one element from the last 2 indices for optimally maximum answer.

**ANOTHER INTERESTING SOLUTION** –

The problem SUPW (ZCO14002) and this problem are very much related. So much so, that a 1-2 line change in the code of either problem can work as the solution for the other problem. This is because of a very simple relation - Sum of elements of array = answer of problem IPL + answer of problem SUPW. The proof of this relation is left on to the readers to be derived.

**TIME COMPLEXITY** -

O(N*2)