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++

Download   Run Code

Output:

Maximum sum is 26

Java

Download   Run Code

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++

Download   Run Code

Output:

Maximum sum is 26

Java

Download   Run Code

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++

Download   Run Code

Output:

Maximum sum is 26

Java

Download   Run Code

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 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

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 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Simra Afreen
Guest

simple solution – space optimized

Ezra Epstein
Guest

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
}

return Math.max(prevMax, adjMax);
}