# Find maximum sum of subsequence with no adjacent elements

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

For example,

Input:  { 1, 2, 9, 4, 5, 0, 4, 11, 6 }
Output: Maximum sum is 26

The maximum sum is formed by subsequence { 1, 9, 5, 11 }

The problem is similar to 0/1 Knapsack problem where for every item, we have two choices – to include that element in the solution or to exclude that element from solution. We can solve this problem by following the same logic. The only difference is that we include current element only if it is not adjacent to previous element considered.

## C++

Output:

Maximum sum is 26

## Java

Output:

Maximum sum is 26

We can also solve this problem in bottom-up fashion using Dynamic Programming (Tabulation). In the bottom-up approach, we solve smaller sub-problems first, then solve larger sub-problems from them. The idea is to create an auxiliary array lookup[] to store solution of sub-problems where for each index i, lookup[i] stores the maximum value that can be attained till index i. It uses value of smaller values i already computed. It has the same asymptotic run-time as Memoization but no recursion overhead.

## C++

Output:

Maximum sum is 26

## Java

Output:

Maximum sum is 26

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

Above solution uses extra space. We can also solve this problem without using any extra space. If we analyze the solution, we can see that maximum sum till any index i can be found by knowing the maximum sum of previous index i-1 and index i-2. So instead of storing the complete array, we can maintain two variables that stores the maximum sum till previous index and previous to previous index.

## C++

Output:

Maximum sum is 26

## Java

Output:

Maximum sum is 26

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
Simra Afreen

simple solution – space optimized

Guest
Ezra Epstein

You can do this even more simply and simultaneously handle the case where the input array may contain non-positive values. Time: O(n), space: O(1).

public int maxNonAdjacentSum(final int[] nums) {
final int N = nums.length;

if (N == 0) {
return 0;
}

// since we're doing summation,
// the starting sums are zero.
int adjMax = 0; // the sum of value where the last number is adjacent to the current value (e.g., i-1)
int prevMax = 0; // the sum of the non-adjacent sequence (e.g., up to an possibly including i-2)

for (int num : nums) { // using a for-each loop means we don't have an actual index 'i', but just pretend.
int tmp = adjMax;
adjMax = Math.max(prevMax + num, prevMax); // compute the new 'adjacent' value
prevMax = Math.max(tmp, prevMax); // and the new 'previous' value
}