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.
这个问题的基础是求最大连续子段和，这里衍生成了多路最大连续子段和。
首先理解题是很费力的，开始理解错了，费了很多脑筋，读不懂，读不明啊，不明白问题点这里，这篇博主把问题讲的应该还算清楚了，本人就是看了这篇题目解释才明白，原来也犯了同样的错。
如果这个例子你得到的结果是 15，那还是看看上面的链接和下面的分析，如果得到的是 11，那请跳过，直接看代码吧。
在求最大连续子段和问题时，我们总是考虑对当前元素的处理，是加入还是不加入到序列里，若加入到序列里，则继续同样处理下一个元素，若不加入，则先前得到的部分和与我无关，我重新做人，丢掉一切从0开始。
那么对于树结构而言，首先我们想到的处理策略都是递归，那么既然递归我们就从底向上开始处理了(从root开始，只能说呵呵了)，这跟DP也很像，抛开特殊情况，我们假设当前处理的节点是 2，那么我们怎么处理2 呢？当然这时2的子树结果已经知道了。
情况1 ：2要单干，独立为王。
1）左右子树都很卖力，很能干，都修成了“正”果，那么就都收了，结果为 2 + 2.left + 2.right
2）左右子树都不是省油的灯，都“负”债累累，果断丢弃，结果为 2 本身。< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+ICAgICAgICAgIDOjqda709DSu7j20N6zyaGw1f2hsbn7o6y94bn7zqogMiAmIzQzOyDV/bXExMe49rfW1qehozwvcD4KPHA+x+m/9jKjuiAyILjQvvXKxrWlwaaxoaOsu/LKx7yvzOXI2dP+utzHv6Os0qrI67vvo6zEx8O0yOu779Kyyse/tMz1vP61xKOsvs3P8c22vbXSssrH0qq/tLPvwuu1xKGjsru5/dKq1Ly3qMj91cKjujwvcD4KPHA+ICAgICAgICAgMaOpMiCyu8TcsNHX89PSt9bWp7a8tPjJz6Os0vLOqsK3vrbKx7Wlz/K1xKOss/3By7alvLa1xEJvc2Ugcm9vdKGjPC9wPgo8cD4gICAgICAgICAyo6kyIL/J0tTSu7j2t9bWp7a8sru0+KOsvs3X1Ly6taW2wMjru++jrNXisrvKx7K7uvG1wKOsysfPwsPmwb249rfW1qfMq7K71fnG+KOstryhsLi6obG1xNK7y/q6/c2/o6zI9LT418XSu8bwyOu776Os0MLAz7Dlt8e1xN/H4OrX1Ly6sru/yaGjPC9wPgo8cD4gICAgICAgICAzo6m0+MnP0ru49rfW1qfKx7/J0tS1xKOstbHIu8rHtPjJz7HIvc+1w8GmtcSjrKGw1f2hscTcwb+9z7jftcShozwvcD4KPHA+09DBy9Xi1Ly3qMj91cKjrDLU2sjru+/HsL7NtcS64sG/19S8usjru+/RodTxwcujrMrH19S8utK7uPa7ucrHtPjJz9K7uPajrNXivs3Sqr+8wsfExNbW0aHU8bvhuPjQws3FzOW0+MC01+6089Cn0uajrLWxyLu+zcrHzOG5qbXEyv3X7rTzwcuhozwvcD4KPHA+usPBy6OszsrM4rv5sb7Ltcfls/7By6Ost9bO9sfls/7By6OsztLDx7+01+7W1bT6wuuwyaGjPC9wPgo8cD4vL2NvZGU8L3A+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:java;">class Solution { public: int max_2(int a, int b) { return a > b a : b; } int max_3(int a, int b, int c) { return max_2(a, max_2(b, c)); } int maxSum(TreeNode *root, int &max_val) { if(!root) return 0; int sum_left = maxSum(root->left, max_val); int sum_right = maxSum(root->right,max_val); int temp1 = max_2(root->val + sum_left, root->val + sum_right); int temp2 = max_2(root->val, root->val + sum_left + sum_right); max_val = max_3(max_val, temp1, temp2); return max_2(root->val,temp1); } int maxPathSum(TreeNode *root) { int max = -0x7f7f7f7f; maxSum(root,max); return max; } };
程序中，maxSum返回的值，就是倘若当前结点要入伙所提供的最大能量。
maxSum函数的max_val参数是当前整体所得到的最大值，这个最大值是可能因为当前结点选择单干或是入伙而产生变化的。
http://blog.csdn.net/shiquxinkong