// 演算法：與 C 版相同。後序 DFS，gain 回傳向下單邊最大和，
// 過程中用 val + 左 + 右 更新成員變數 best；負貢獻 clamp 成 0。
// Algorithm: identical to the C version. Post-order DFS; gain returns the best single-side
// downward sum, while member variable best is updated with val + left + right; negatives clamped to 0.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    // 用成員變數保存目前看過的最大路徑和，取代 C 版的指標傳遞
    // A member variable holds the running best, replacing the C version's pointer passing
    int best = INT_MIN;   // INT_MIN 來自 <climits>，是最小的 int / INT_MIN (from <climits>) is the smallest int

    // 回傳「從 node 只往下走一條直線」的最大貢獻
    // Returns the best contribution going straight down from node
    int gain(TreeNode* node) {
        if (!node) return 0;   // 空指標視為 0 貢獻 / a null pointer contributes 0

        // std::max(0, x) 把負貢獻夾成 0；<algorithm> 提供 std::max
        // std::max(0, x) clamps negative gains to 0; std::max comes from <algorithm>
        int left  = std::max(0, gain(node->left));    // 遞迴左子樹 / recurse left
        int right = std::max(0, gain(node->right));   // 遞迴右子樹 / recurse right

        // 以 node 為轉彎點、同時納入左右的完整路徑候選
        // Candidate path bending at node, using both sides
        best = std::max(best, node->val + left + right);

        // 交給父節點時只能保留較大的一邊 / hand only the larger side up to the parent
        return node->val + std::max(left, right);
    }

public:
    int maxPathSum(TreeNode* root) {
        gain(root);     // 一趟 DFS 就把 best 算好 / a single DFS fills in best
        return best;    // 回傳最終答案 / return the final answer
    }
};