Embercode: AI-powered software engineer course

1. What does this program print? ``

cpp
#include <algorithm>
#include <iostream>

struct Info {
    long long total, prefix, suffix, best;
};

Info leaf(long long v) { return {v, v, v, v}; }

Info merge(const Info& a, const Info& b) {
    return {a.total + b.total,
            std::max(a.prefix, a.total + b.prefix),
            std::max(b.suffix, b.total + a.suffix),
            std::max({a.best, b.best, a.suffix + b.prefix})};
}

int main() {
    Info x = merge(merge(leaf(-4), leaf(3)), leaf(-1));
    std::cout << x.best << ' ' << x.prefix << ' ' << x.suffix << ' ' << x.total << '\n';
}

``

3 -1 -2 2-1 3 2 -23 -1 2 -23 2 -1 -2

2. What does this program print? ``

cpp
#include <algorithm>
#include <iostream>

struct Info {
    long long total, prefix, suffix, best;
};

Info leaf(long long v) { return {v, v, v, v}; }

Info merge(const Info& a, const Info& b) {
    return {a.total + b.total,
            std::max(a.prefix, a.total + b.prefix),
            std::max(b.suffix, b.total + a.suffix),
            std::max({a.best, b.best, a.suffix + b.prefix})};
}

int main() {
    Info y = merge(leaf(-3), leaf(-1));
    std::cout << y.total << ' ' << y.best << '\n';
}

``

-4 0-4 -1-1 -4-3 -1

3. In the merge rule for best, why is a.suffix + b.prefix included?

It gives the total of the whole rangeIt is the best prefix of the whole rangeIt stops the answer from ever being negativeIt covers a subarray that crosses the middle, which neither child can see alone

4. Which formula is the merge rule for prefix in lesson 14?

max(A.prefix, A.total + B.prefix)max(A.prefix, B.prefix)max(B.suffix, B.total + A.suffix)A.total + B.prefix

5. True or false: a zero-filled Info can serve as the empty answer for a query that covers no positions, because its best value of 0 never beats a real answer.

True, because 0 is never larger than a real subarray sum, so it can be left out of any mergeFalse, because best 0 beats any all-negative range, so an all-negative range would wrongly return 0

Node merging