Maximum path sum

Questions 1 to 5 of 6

1. 1. In the maximum path sum method, why does a node send only its value plus the larger clipped child gain up to its parent, not the sum of both children?

   Because the parent's value is always added twiceBecause a path that continues upward is one straight line and cannot use both children of a nodeBecause clipping only applies to the rootBecause the answer must always end at a leaf
2. 2. A child has gain -4. What does clipping do to it?

   It removes the parent node from the treeIt flips the sign, so the child adds 4 to the pathIt adds -4 anyway, because a path must include every childIt replaces the gain with 0, so the path does not go into that child
3. 3. What does this program print? ``cpp #include <algorithm> #include <iostream> #include <limits> #include <memory> struct Node { int val = 0; std::unique_ptr<Node> left, right; }; std::unique_ptr<Node> mk(int v, std::unique_ptr<Node> l = nullptr, std::unique_ptr<Node> r = nullptr) { auto n = std::make_unique<Node>(); n->val = v; n->left = std::move(l); n->right = std::move(r); return n; } long long gain(const Node* n, long long& best) { if (n == nullptr) return 0; long long left = std::max(0LL, gain(n->left.get(), best)); long long right = std::max(0LL, gain(n->right.get(), best)); best = std::max(best, n->val + left + right); return n->val + std::max(left, right); } long long maxPathSum(const Node* root) { long long best = std::numeric_limits<long long>::min(); gain(root, best); return best; } int main() { auto t = mk(5, mk(3), mk(-4)); std::cout << maxPathSum(t.get()) << '\n'; } ``

   438-4
4. 4. What does this program print? ``cpp #include <algorithm> #include <iostream> #include <limits> #include <memory> struct Node { int val = 0; std::unique_ptr<Node> left, right; }; std::unique_ptr<Node> mk(int v, std::unique_ptr<Node> l = nullptr, std::unique_ptr<Node> r = nullptr) { auto n = std::make_unique<Node>(); n->val = v; n->left = std::move(l); n->right = std::move(r); return n; } long long gain(const Node* n, long long& best) { if (n == nullptr) return 0; long long left = std::max(0LL, gain(n->left.get(), best)); long long right = std::max(0LL, gain(n->right.get(), best)); best = std::max(best, n->val + left + right); return n->val + std::max(left, right); } long long maxPathSum(const Node* root) { long long best = std::numeric_limits<long long>::min(); gain(root, best); return best; } int main() { auto t = mk(-3, mk(-1), mk(-2)); std::cout << maxPathSum(t.get()) << '\n'; } ``

   -10-3-6
5. 5. True or false: if every value in the tree is negative, maxPathSum returns 0, because clipping sets every gain to 0.

   True, because clipping sets every gain to 0 and the empty path has sum 0True, because best starts at 0 whenever all values are negativeFalse, because a path must have at least one node, so the answer is the largest single nodeFalse, because the answer is always the value of the root