PROBLEM LINK:
DIFFICULTY:
MEDIUM-HARD
PROBLEM:
Find the maximum sum that can be formed without selecting adjacent elements.
EXPLANATION:
This problem is inspired by the SPOJ problem FARIDA.
The first approach is to generate the power set and check if each subset satisfies the condition that no there are no adjacent elements. If the subset satisfies the check, then find the sum. In this manner, find the maximum sum that can be formed.
This approach has the complexity O(n*2n)
The second approach is by using recursion. If we select the current element, then we cannot select the next element and we can skip it. If we don’t select the current element, then we can think about selecting the next element. Following are two versions of the recursive code.
fun(arr,i,n,sum=0)
{
if(i>=n)
return sum;
return max(fun(arr,i+2,n,sum+arr[i]),fun(arr,i+1,n,sum));
}
func(arr,n)
{
if(n<0)
return 0;
return max(func(arr,n-2)+arr[n],func(arr,n-1));
}
This approach has the complexity O(2n)
The next is a Dynamic Programming approach which can find the maximum sum in just O(n). We can populate the DP array in a bottom-up fashion as follows:
for(i=0;i<n;i++)
{
if(i==0)
dp[i]=a[i];
else if(i==1)
dp[i]= max(a[0],a[1]);
else
dp[i]=max(dp[i-2]+a[i],dp[i-1]);
}
Finally the answer will be available in dp[n-1].
Comparing the second and the third approach can yield some similarities. The recursive code is slower because it checks all possibilities, even the ones where no elements are selected. The DP approach does not check all possibilities. It stores the best possible answer in each step.