Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

``````       1
/ \
2   3
``````

Return `6`.

localMax = max(v, v + leftChild, v + rightChild, v + leftChild + rightChild)

globalMax = max(globalMax, localMax)

``````
class Solution {
public:
int maxSum;

int recursiveFindMaxSum(TreeNode* node)
{
if(node)
{
int lval = 0;
if(node->;left) lval = recursiveFindMaxSum(node->;left);
int rval = 0;
if(node->right) rval = recursiveFindMaxSum(node->right);

if(lval < 0) lval = 0;
if(rval < 0) rval = 0;

int localMax = max(node->val, node-&amp;gt;val + lval + rval);
maxSum = max(maxSum, localMax);

localMax = max(node->val, max(node->val + lval, node->val + rval));
return localMax;
}
}

int maxPathSum(TreeNode* root)
{
maxSum = 0x80000000;
if(root)
{
recursiveFindMaxSum(root);
}
return maxSum;
}
};
O(n), 26ms
``````