Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree.

Example

1
/ \
2 3
Max Path Sum = 6

The following algorithm uses recursion to find vertical maximum path sum, which is the maximum path sum from a node down to its descendant. Then the vertical path sum is used to find cross maximum path sum, which is from child to child.