Question

Given a binary tree encoded as a level-order array (None marks a missing child; values may be negative), return the maximum path sum. A path is any sequence of nodes connected by edges where each node appears at most once; it does not need to pass through the root and need not be root-to-leaf. Use a post-order pass where each node returns the best downward gain (max single-branch contribution, clamped at 0) while a global best tracks the best 'arch' (left gain + node + right gain). Return the maximum path sum.