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

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

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

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).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂