No adjacent elements


#1

write a program for:
Given an array of integers,find the maximum sum of subsequence of given array where subsequence contains no adjacent elements.


#2

This problem can be looked like, you have array a index 0 to n-1.
Consider another array m where m[i] indicate the maximum sum of subsequence of a[i…n-1] where subsequence contains no adjacent elements. So our goal is to find m[0].
As base case, m[n-1] will be a[n-1].
m[n-2] = max sum of subsequence of array([a[n-2] , a[n-1]) which will be max of (a[n-2], a[n-1]) because if we took n-2 th element, we can’t consider the n-1th element
m[n-3] = max(a[n-3]+m[n-1], m[n-2])
So for ith element m[i] = max(a[i]+m[i+2], m[i+1]) because if we take ith element in sum, we need to skip i+1th and get the max subsequence sum of a[i+2…n-1] which is already stored in m[i+2].
Algorithm:

/**
* It assume that array has only positive elements. If it has negative elements, use the commented code part.
*/
int getMaxSubseqSum(int a[], int n)
{
	if(n == 0)
		return 0;
	if(n == 1)
		return a[0];
	int[] m = new int[n];
	m[n-1] = a[n-1];
	m[n-2] = max(a[n-2], m[n-1]);
	for(int i = n-3; i>= 0; --i)
	{
		m[i] = max(a[i]+m[i+2], m[i+1]); //For negative array, replace it with max(a[i]+m[i+2], m[i+1], m[i+2])
	}
	return m[0];
}