Binary Tree Maximum Path Sum

1def maxPathSum(root):
2  max_sum = float('-inf')
3
4  def maxGain(node):
5    nonlocal max_sum
6
7    if not node:
8      return 0
9
10    # Get max gain from left and right (ignore negative)
11    left_gain = max(maxGain(node.left), 0)
12    right_gain = max(maxGain(node.right), 0)
13
14    # Check if path through this node is the new max
15    path_sum_through_node = node.val + left_gain + right_gain
16    max_sum = max(max_sum, path_sum_through_node)
17
18    # Return max gain from this node (can only go one way)
19    return_value = node.val + max(left_gain, right_gain)
20    return return_value
21
22  maxGain(root)
23  return max_sum