## What will the maximum path look like

Though paths can be starting from any node and end at any node, the appearances only can be:

• Appearance 1
``````      *
/ \
*   *
/     \
*       *
/         \
S           *
\
E
``````
• Appearance 2
``````      E
/
*
/
*
/
S
``````
• Appearance 3
``````S
\
*
\
*
\
*
\
E
``````

### Note

Appearances above are only talking about `TRUNK`.

Treat the path below as Appearance 1

``````      *
/ \
*   *
/     \
*       *
\     /
S   *
\
E
``````

## Tree Version of Maximum Subarray

• Appearance 2/3

These two appearances are easy to understand and to build a path, just take the maximum node. like `Maximum Subarray`, if the sum goes below `0`, forget the old nodes.

• Appearance 1

If a node's left child or right child is less than `0`, drop it, then the node becomes `Appearance 2/3`.

If both the left child and right child are positive, just add them together, `maxPathSum(node.left) + node.val + maxPathSum(node.right)` will be the `maxPathSum` which contains that node.

## Put them together

As we know how to find the `maxPathSum` of any node, we can go through the tree and update the max value.