Graph Theory37 sections · 1633 units
Open in Course

LeetCode 124 Binary Tree Maximum Path Sum - Handling Negatives

Skip negative branches

If a child returns a negative value, do not include it in your path. Taking a negative branch decreases your sum, which is never best. Use max( ext{dp}[ ext{child}], 0) when computing values.

This means "take the child path only if it helps (is positive)." For a leaf node, ext{dp}[v] = v (the node value itself). If vv is negative, the parent might skip it. The parent compares including vv vs taking 00 (not going down that branch at all).