// 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.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root) {
        if(root == null) return 0;
        int[] res = new int[1];
        res[0] = Integer.MIN_VALUE;

        dfs(root, res);

        return res[0];
    }

    public int dfs(TreeNode node, int[] res){
    	if(node == null) return 0;

    	int left = dfs(node.left, res) ;
    	int right = dfs(node.right, res) ;

    	// currentMax candidates(open path not closed, path should be able to extend): 
    	//	1. node; 2. node + single child.
    	int currentMax = Math.max(node.val, left > right? left + node.val : right + node.val);

    	// globalMax candidates:(both open&closed path should be considered):
    	// 1.stored max; 2.node; 3.node + single child; 4.node + both children.
    	int globalMax = Math.max(res[0], Math.max(node.val, Math.max(left + node.val + right, left > right? node.val + left : node.val + right)));

    	res[0] = globalMax;

    	return currentMax;
    }
}
@@ -1,381 +1,4 @@
-// Given a binary tree, find the maximum path sum.%0A%0A// The path may start and end at any node in the tree.%0A%0A// For example:%0A// Given the below binary tree,%0A%0A//        1%0A//       / %5C%0A//      2   3%0A// Return 6.%0A%0A/**%0A * Definition for binary tree%0A * public class TreeNode %7B%0A *     int val;%0A *     TreeNode left;%0A *     TreeNode right;%0A *     TreeNode(int x) %7B val = x; %7D%0A * %7D%0A */%0A
 publ
@@ -269,17 +269,20 @@
 s)%7B%0A    
-%09
+    
 if(node 
@@ -301,25 +301,28 @@
 urn 0;%0A%0A    
+  
-%09
+  
 int left = d
@@ -342,25 +342,28 @@
  res) ;%0A    
+   
-%09
+ 
 int right = 
@@ -390,17 +390,20 @@
  ;%0A%0A    
-%09
+    
 // curre
@@ -482,12 +482,16 @@
     
-%09//%09
+    //  
 1. n
@@ -519,25 +519,28 @@
  child.%0A    
-%09
+    
 int currentM
@@ -619,17 +619,20 @@
 );%0A%0A    
+ 
-%09
+   
 // globa
@@ -697,17 +697,20 @@
 d):%0A    
-%09
+    
 // 1.sto
@@ -777,17 +777,20 @@
 en.%0A    
-%09
+//  
 int glob
@@ -920,22 +920,96 @@
 ght)));%0A
-%0A
+        int globalMax = Math.max(node.val + left + right, currentMax);%0A%0A  
     
-%09
+  
 res%5B0%5D =
@@ -1022,16 +1022,48 @@
 lMax
+ %3E res%5B0%5D? globalMax : res%5B0%5D
 ;%0A%0A    
-%09
+    
 retu

update path sum solution