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)