Majority and subarray

Questions 1 to 5 of 6

1. 1. What does this program print? ``cpp #include <algorithm> #include <iostream> #include <limits> #include <span> #include <vector> long long bestAcrossMiddle(std::span<const int> left, std::span<const int> right) { long long bestLeft = std::numeric_limits<long long>::min(); long long run = 0; for (auto it = left.rbegin(); it != left.rend(); ++it) { run += *it; bestLeft = std::max(bestLeft, run); } long long bestRight = std::numeric_limits<long long>::min(); run = 0; for (int x : right) { run += x; bestRight = std::max(bestRight, run); } return bestLeft + bestRight; } int main() { std::vector<int> v = {-4, 6, -1, 2, -7, 3}; std::span<const int> s(v); std::cout << bestAcrossMiddle(s.first(3), s.subspan(3)) << '\n'; } ``

   5723
2. 2. What does this program print? ``cpp #include <algorithm> #include <iostream> #include <span> #include <vector> int countIn(std::span<const int> a, int value) { return static_cast<int>(std::ranges::count(a, value)); } int candidate(std::span<const int> a) { if (a.size() == 1) return a[0]; auto mid = a.size() / 2; int left = candidate(a.first(mid)); int right = candidate(a.subspan(mid)); if (left == right) return left; if (countIn(a, left) > static_cast<int>(a.size() / 2)) return left; return right; } int main() { std::vector<int> nums = {7, 8, 7, 8}; int c = candidate(nums); std::cout << "candidate " << c << ", count " << countIn(nums, c) << '\n'; } ``

   candidate 7, count 2candidate 8, count 3candidate 8, count 2candidate 7, count 4
3. 3. Why does majorityElement count the candidate one more time after candidate returns?

   Because candidate may return a value that never appears in the array.Because the count is needed to find which half the majority element lies in.Because the combine rule compares only two candidates, so it never sees the whole array.Because candidate returns a guess that can be wrong, such as 4 for 1 2 3 4, and only the count shows whether it is a real majority.
4. 4. In maxSubarray, why does the crossing case need its own check, separate from the two recursive answers?

   Because the recursive calls can only return positive sums, so negative crossing sums must be added separately.Because a crossing subarray is always larger than any subarray that lies inside one half.Because each recursive call sees only its own half, so a subarray that uses elements from both halves, such as 4 -1 2 1 in the lesson's example, is never counted by them.Because the recursion stops at blocks of size 2, so the two halves are never compared.
5. 5. The combine step below has one wrong line. The rest of the code matches the lesson. ``cpp int candidate(std::span<const int> a) { if (a.size() == 1) return a[0]; auto mid = a.size() / 2; int left = candidate(a.first(mid)); int right = candidate(a.subspan(mid)); if (left == right) return left; if (countIn(a, left) > static_cast<int>(a.size() / 2)) return left; return left; } ` What does majorityElement({2, 1, 1})` return, and what should it return?

   It returns nothing. The last line should return right, and then the answer is 1, because 1 appears 2 times, which is more than 3 / 2 = 1.It returns 2. The left == right check is backwards, and the left candidate should lose every tie.It returns nothing, which is correct, because a majority needs all 3 values to match.It returns 2. The bug is in countIn, which should count only the left half, and the correct answer is also 2.