# My java solution

• basic idea is the few lines of comment in the beginning of maxPathSum2(). this method returns 2 numbers, the best COMPLETE path under this current root, not necessarily including root; and the best path ending at root, called "partial" . the formulation of the problem does not allow null to be considered a path of cost 0, so I had to do a lot of tweaks which made the flow look less nice

``````/**
* 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) {
return maxPathSum2(root)[0];
}

int[]  maxPathSum2(TreeNode root) {
// (fullLeft, halfLeft ) = maxPathSum(root.left);
// (fullRight, halfRight) = maxPathSum(root.right);

// return { max(fullLeft , fullRight, halfLeft + root.val + halfRight ),
//   max(halfLeft, halfRight) + root.val
// };
if (root == null) return new int[]{Integer.MIN_VALUE, Integer.MIN_VALUE};

int left[] = maxPathSum2(root.left);
int right[] = maxPathSum2(root.right);

// if the sub trees produce negative , just ignore
// left[0] = Math.max(0, left[0]);
// left[1] = Math.max(0, left[1]);
// right[0] = Math.max(0, right[0]);
// right[1] = Math.max(0, right[1]);

int full = root.val;
if (root.left != null && left[1] >0 )
full+= left[1];

if (root.right !=null && right[1] > 0 )
full += right[1];

int partial = root.val;
if (root.left !=null) {
full = Math.max(full, left[0]);
partial = Math.max(partial, root.val + left[1]);
}

if (root.right !=null) {
full = Math.max(full, right[0]);
partial = Math.max(partial, root.val + right[1]);
}

return new int[]{
full,
partial
};
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.