# Golang solution (39ms)

• Maintain a global `maxSum` to keep track of the maximum path sum seen so far.
• At every node we need to compare the maximum of four values:
(1) The node itself
(2) The node + maximum path sum of the left subtree
(3) The node + maximum path sum of the right subtree
(4) The node + maximum path sum of both the left and right subtrees
• We compute the max of #1, #2, #3 and assign it to `maxSumEndingAtNode`
• Then we update the global `maxSum` with the maximum of either #4 or `maxSumEndingAtNode`.
• Finally, we return `maxSumEndingAtNode`, since this value represents the maximum path sum of the subtree rooted at this node.
``````func maxPathSum(root *TreeNode) int {
maxSum := math.MinInt32
maxPathSumHelper(root, &maxSum)
return maxSum
}

func maxPathSumHelper(node *TreeNode, maxSum *int) int {
if node == nil { return 0 }
left, right := maxPathSumHelper(node.Left, maxSum), maxPathSumHelper(node.Right, maxSum)
maxSumEndingAtNode := max(node.Val, node.Val + max(left, right))
*maxSum = max(*maxSum, max(node.Val + left + right, maxSumEndingAtNode))
return maxSumEndingAtNode
}

func max(x, y int) int { if x > y { return x }; return y }
``````

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