ZCO14004 - Editorial

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)

1 Like