Maximum sum path between 2 nodes

#1

So here we have 4 cases.
My question should not my contribution to my root be the maximum of 4, why is it
max(left, right , 0) + root->data , i dont understand this.

#2

@sounakume you have to add the current node’s value no matter what. This is why it is added, and not considered in max(left, right, 0). Because no matter what path you choose you will always have to consider the current node.

#3

but why, shouldn’t my contribution to my parent be the max of 4 cases, why add root no matter what, im not getting this.

#4

@sounakume how will the code work if you are not considering the current element at all? How will the recursion work if you are not doing any work for the smaller subproblem? You can try to dry run by taking the max of 4 cases but then you will see it is giving wrong answer.

1 Like