algo: max sum path in a tree

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6. Because you can go from 2 to 3 (via 1) and the total sum is 6

http://www.leetcode.com/onlinejudge

A very good test case is:

Given the below binary tree,

                           9
                          / \
                        6     -3
                       / \   /  \
                      #   # -6   2
                           / \  /  \
                          #  #  2   #
                              /   \
                            -6     -6
                           /
                          -6

Return 16. Because you can go from 6 to 2 (via 9, -3, 2) and the sum is 16, which is the max you can get from any two nodes. Here # means NULL

Assume we knew the path for the max sum.  We calculate the local maxPathSum that HAS TO include the current node. Compare this local max to the historical max value of the other nodes, and the record the new max.

The local max path must be done recursively with every node: max(maxSumPath(root->left), maxSumPath(root->right))

To find the local max, simply speaking, the path should start from a node in left subtree, go pass node(9), and end at a node in right subtree. When the pass starts from left subtree to node(9), it is a one-way-up path where I call it a single path. This single path has to be maximum when it reaches node(9). So the maxSinglePath of the left subtree is 6. Similarly, the maxSinglePath of the right subtree is 1.

When updating the maxSinglePath, there are 3 sub-cases:
case A: left subtree has a negative maxSinglePath. (returns root+right = 21)
case B: right subtree has a negative maxSinglePath. (returns root+left = 17)
case C: both subtrees have negative maxSinglePath. (returns root = 15)
     15                         15                              15
     / \                         /  \                             /  \
 -3    6                     2     -7                       -3    -5

So the maxSinglePath of the root is max(root+left,  root+right, root)

class Solution {
public:
    int maxValue;
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int singleDown;
        maxValue = -9999;
        return maxPathOverload(root, singleDown);
    }
    int maxPathOverload(TreeNode* root, int& singleLine){
        if (!root){
            singleLine = 0;
            return 0;
        }
        int leftSingleLine = 0;
        int rightSingleLine = 0;
        maxPathOverload(root->left, leftSingleLine);
        maxPathOverload(root->right, rightSingleLine);
        vector subMaxPath;
        subMaxPath.push_back(root->val);//case C
        subMaxPath.push_back(root->val + leftSingleLine);//case B
        subMaxPath.push_back(root->val + rightSingleLine);//case A
        singleLine = *max_element(subMaxPath.begin(), subMaxPath.end());
        subMaxPath.push_back(root->val + leftSingleLine + rightSingleLine);//case 1
        maxValue = max(maxValue, *max_element(subMaxPath.begin(), subMaxPath.end()));
        //compare the path values, which you HAVE TO include the current node
        //This eleminate the zero's for null leaf's
        
        return maxValue;       
    }
};