# Woodstock Blog

## a tech blog for general algorithmic interview questions

### Question

Given an array of positive numbers, find the maximum sum of a subsequence that no 2 numbers should be adjacent.

Eg. (3, 2, 7, 10) should return 13 (3+10)

Eg. (3, 2, 5, 10, 7) should return 15 (3+5+7).

### Solution

It is an modified version of “max sum subsequence”. Answer given on gfg is:

Loop for all elements in arr[] and maintain two sums ‘incl’ and ‘excl’ where:

incl = Max sum including the previous element

excl = Max sum excluding the previous element

### Code

written by me

``````public int solve(int[] A) {
if (A == null || A.length == 0) {
return 0;
} else if (A.length == 1) {
return A[0];
} else if (A.length == 2) {
return Math.max(A[0], A[1]);
}

int prePreMax = A[0];
int preMax = A[1];
int ans = 0;

for (int i = 2; i < A.length; i++) {
ans = Math.max(ans, prePreMax + A[i]);
// set the 2 variables: prePreMax, preMax
int temp = preMax;
preMax = Math.max(0, prePreMax + A[i]);
prePreMax = Math.max(prePreMax, temp);
}
return ans;
}
``````