Algorithm to find the maximum non-adjacent sum in n-ary tree

Question

Given an n-ary tree of integers, the task is to find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should share a common edge in the tree. Example: 1 / \ 2 5 / \ 3 4 Maximum non adjacent sum = 3 + 4 + 5 = 12 The following is the faulty extension of the algorithm outlined in http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent?

def max_sum(node, inc_sum, exc_sum):
    for child in node.children:
        exc_new = max(inc_sum, exc_sum)
        inc_sum = exc_sum + child.val
        exc_sum = exc_new
        inc_sum, exc_sum = max(max_sum(child, inc_sum, exc_sum),
                               max_sum(child, inc_sum, inc_sum - node.val))
    return exc_sum, inc_sum

But I wasn't sure if swapping exc_sum and inc_sum while returning is the right way to achieve the result and how do I keep track of the possible sums which can lead to a maximum sum, in this example, the maximum sum in the left subtree is (1+3+4) whereas the sum which leads to the final maximum is (3+4+5), so how should (3+4) be tracked? Should all the intermediary sums stored in a table?

I guess I don't quite get the example - shall the paths to the nodes labelled with the terms for the sum be disjunct (no shared ancestor but possibly the root) or shall no two such nodes be siblings? — greybeard
– greybeard, Commented Mar 5, 2015 at 8:57
@maverickz were you satisfied with answer or do you still have doubts ? — advocateofnone
– advocateofnone, Commented Mar 6, 2015 at 4:57
@greybeard: As per the problem description no two nodes which are included in the sum can share an edge i.e can't have a parent-child relationship — maverickz
– maverickz, Commented Mar 6, 2015 at 8:18
@sasha: The solution is neat! Sorry I couldn't up vote it for lack of reputation. Also can this algorithm be extended to a graph and if so should we consider the max of all sums with each of the nodes as the starting node? — maverickz
– maverickz, Commented Mar 6, 2015 at 8:42

advocateofnone · Accepted Answer · 2015-03-05 08:10:48Z

4

Lets say dp[u][select] stores the answer: maximum sub sequence sum with no two nodes having edge such that we consider only the sub-tree rooted at node u ( such that u is selected or not ). Now you can write a recursive program where state of each recursion is (u,select) where u means root of the sub graph being considered and select means whether or not we select node u. So we get the following pseudo code

     /* Initialize dp[][] to be -1 for all values (u,select) */
     /* Select is 0 or 1 for false/true respectively        */

     int func(int node , int select )
     {
         if(dp[node][select] != -1)return dp[node][select];
         int ans = 0,i;

         // assuming value of node is same as node number
         if(select)ans=node;

         //edges[i] stores children of node i
         for(i=0;i<edges[node].size();i++)
         {
             if(select)ans=ans+func(edges[node][i],1-select);
             else ans=ans+max(func(edges[node][i],0),func(edges[node][i],1));
         }
         dp[node][select] = ans;
         return ans;
     }

     // from main call, root is root of tree and answer is
     // your final answer
     answer = max(func(root,0),func(root,1));

We have used memoization in addition to recursion to reduce time complexity.Its O(V+E) in both space and time. You can see here a working version of the code Code. Click on the fork on top right corner to run on test case
4 1
1 2
1 5
2 3
2 4
It gives output 12 as expected.
The input format is specified in comments in the code along with other clarifications. Its in C++ but there is not significant changes if you want it in python once you understand the code. Do post in comments if you have any doubts regarding the code.

edited Mar 5, 2015 at 8:10

answered Mar 5, 2015 at 7:31

advocateofnone

2,5393 gold badges20 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

maverickz Over a year ago

Shouldn't the test case be 4 1 1 2 1 5 2 3 2 4

advocateofnone Over a year ago

I have specified the input format and given a link you can run on your testcases also

maverickz Over a year ago

Sorry, I didn't realize that the first two arguments are the number of edges and the root node and thought that they were parent child nodes as well.

Collectives™ on Stack Overflow

Algorithm to find the maximum non-adjacent sum in n-ary tree

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related