write a program for:

Given an array of integers,find the maximum sum of subsequence of given array where subsequence contains no adjacent elements.

# No adjacent elements

**Harsha_1997**#1

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];
}
```