 #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.
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;
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;
}``````