Module assignment: array toolkit

What you will build

This assignment brings the whole module together in one program. You will write a C++ command-line tool that reads a daily sales log, then answers a list of commands about it. The log may contain negative days, because a day can lose money after refunds. Two kinds of command appear. The first asks for the total of a range of days. The second asks for the best run of consecutive days, meaning the stretch of days with the largest total.

You will use every idea from the module. The log is stored in a vector, from the vectors lesson. The range totals use prefix sums, from the prefix sums lesson. The best run uses a one-pass scan with running totals, the same idea as Kadane's algorithm. You will also use the index discipline from the first and last lessons, because most mistakes in this assignment are off-by-one errors on the boundaries.

Most of the assignment is about correctness. A program that produces the right answer on every input is worth far more than a fast program that is wrong on the edges. The rubric at the end says exactly what each level of quality looks like, so you can judge your own work before you hand it in.

The input

The program reads from standard input, and every number and word is separated by whitespace. Read them in this order.

1. A line with one integer n, the number of days. It satisfies 1 <= n <= 1000.
2. A line with n integers, the profit of each day in order. Each value is between -1000 and 1000 inclusive.
3. A line with one integer q, the number of commands. It satisfies 1 <= q <= 1000.
4. Then q lines, each holding one command. A command is either sum l r, with two integers, or the single word best.

Days are numbered from 0. In sum l r, both l and r are included, and they satisfy 0 <= l <= r < n. You may assume every command is well formed, so you do not need to check the input for errors. Read each command as a word first, then read its numbers only if the word is sum.

The output

Each command produces exactly one line of output, in the order the commands appear.

• For sum l r, print the total profit of days l through r, as one integer, followed by a newline.
• For best, print the text best, then the best total, then the text from, then the first day of the best run, then the text to, then the last day of the best run, all separated by single spaces. The line ends with a newline.

The best run is a non-empty block of consecutive days. Its total can be negative, if every day is negative. If several runs share the largest total, choose the run that ends first. If two of those runs also end on the same day, choose the one that starts first. This tie rule is part of the specification. Your output must match it exactly, because the grader compares the text character by character.

Two worked examples

Here is the first example. Study it before you start, because it covers the tie rule.

7
4 -2 5 -1 -4 3 2
3
sum 0 2
sum 3 6
best

The program should print:

7
0
best 7 from 0 to 2

The first command adds days 0, 1 and 2, which are 4, -2 and 5, giving 7. The second adds days 3 to 6, which are -1, -4, 3 and 2, giving 0. The third command asks for the best run. The run from day 0 to day 2 totals 7. The run from day 0 to day 6 also totals 7, because the last four days cancel out, so there is a tie. The tie rule says the run that ends first wins, and day 2 comes before day 6. So the answer is best 7 from 0 to 2.

Here is the second example, which covers an all-negative log.

4
-3 -1 -2 -5
2
best
sum 1 1

The program should print:

best -1 from 1 to 1
-1

Every day is negative, so the best run is the single least negative day. Day 1 holds -1, which is larger than every other single day. The run must contain at least one day, so the answer is -1, not 0. The second command asks for day 1 alone, which is -1.

Requirements checklist

Copy this list into your own notes, and tick each item when your program satisfies it. Each item is something a grader will check.

• The program reads n, then the n daily values, into a vector of long long.
• The program builds the prefix sums in one pass, with prefix[0] equal to 0.
• Each sum l r command is answered with one subtraction, using prefix[r + 1] - prefix[l].
• Each best command returns the largest total of a non-empty run of consecutive days.
• The tie rule is applied exactly: the run that ends first wins, and then the run that starts first.
• A log with all negative values returns the least negative single day, not 0.
• A log with n equal to 1 works for both command types.
• Every answer is printed on its own line, with no extra spaces before or after the numbers.
• Commands are processed in the order they appear, and every command prints exactly one line.
• All sums use long long, so a long log of large values does not overflow.
• The program compiles with g++ -std=c++17 -Wall -Wextra and produces no warnings.
• The program has been checked against both worked examples in this assignment, and the output matches exactly.

Grading rubric

The grade depends on correctness first, then on the speed of the best command. The three levels below describe what each score looks like in practice.

60 percent: the sum commands are right, and the best command works on simple logs. The program answers every sum command correctly, using prefix sums or a direct loop. For best, it finds the largest total of a run, but it may get the tie rule wrong, or it may print 0 for an all-negative log. The program compiles, reads the input correctly, and prints one line per command. A run that is correct on the first example but not on the second is a 60 percent solution.

80 percent: everything is correct, including ties and all-negative logs. The best command follows the tie rule exactly, starts from a real day, and handles one-day logs. The implementation may check every pair of days, which is O(n squared) per best command. That is acceptable for this assignment, because the limits are small. The output matches both examples and passes a brute-force check on random inputs.

100 percent: everything is correct, and the best command runs in O(n) per query. The program builds prefix sums once, then scans the days in one pass for each best command, keeping the smallest earlier prefix sum and its position. The code is clear, the names say what each variable holds, and the program uses long long throughout. A grader who reads the code should be able to explain the tie rule from the variable names and comments alone.

The rubric is about the program's behaviour, so you can check your own grade by running the examples and a few edge cases. You do not need to make the program fast beyond O(n) per command.

Hints

Each hint below opens on its own. Try the problem for at least ten minutes before you open one, and stop as soon as you have the next step.

Testing your program

A good way to test this assignment is to compare your program with a slow version that is easy to trust. The slow version tries every pair of days, adds each run directly, and keeps the first run it finds with the largest total when it scans ends first and then starts first. Generate random logs with small values, so that ties happen often, and random commands. Run both versions on each input and compare the output. Any mismatch shows you a case your program gets wrong, and that case is the one to study. Most mismatches come from the tie rule or from an off-by-one error on a boundary.

Keep the test inputs small at first. A log of five to nine days is enough to reveal almost every mistake, and it is easy to check on paper. Once the small tests pass, try a few larger logs, and check that the answer for each best command is still the same as the slow version.

Reference solution

Read this only after you have a solution of your own, or after you have tried the hints. Compare it with your program, and explain each difference in your own words. The code uses one vector for the prefix sums, one loop for each best command, and the tie rule written as a strict comparison.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    // prefix[k] is the sum of days 0 to k - 1.
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + a[i];
    }
 
    int q;
    cin >> q;
    while (q--) {
        string cmd;
        cin >> cmd;
        if (cmd == "sum") {
            int l, r;
            cin >> l >> r;
            cout << prefix[r + 1] - prefix[l] << "\n";
        } else if (cmd == "best") {
            // Scan the end r from left to right. For each r, the best start is
            // the smallest prefix[l] with l <= r, and the earliest such l wins.
            bool have = false;
            long long bestSum = 0;
            int bestL = 0;
            int bestR = 0;
            long long minPrefix = prefix[0];
            int minIndex = 0;
            for (int r = 0; r < n; r++) {
                if (prefix[r] < minPrefix) {
                    minPrefix = prefix[r];
                    minIndex = r;
                }
                long long s = prefix[r + 1] - minPrefix;
                if (!have || s > bestSum) {
                    have = true;
                    bestSum = s;
                    bestL = minIndex;
                    bestR = r;
                }
            }
            cout << "best " << bestSum << " from " << bestL << " to " << bestR << "\n";
        }
    }
    return 0;
}

The reference scans each best command in O(n) time, and it uses O(n) extra space for the prefix sums. The sum commands are O(1) each. Read the tie logic twice. The strict < in the prefix update keeps the earliest start. The strict > in the best update keeps the earliest end. Together they implement the rule in the specification.

Stretch extension

If you finish early and want more practice, extend the program with a third command, window k, which prints the largest total of any run of exactly k consecutive days, in the form window SUM from L to R, with the same tie rule. Use a sliding window for this command, and explain in a comment why it is O(n) per query. Also think about how you would answer best in O(log n) per query after one O(n) build, and write down your idea even if you do not code it. That idea leads to the segment trees you will meet later in the course.

What you have practised

This assignment uses vectors to store the log, prefix sums to answer range questions, a one-pass scan with a strict tie rule for the best run, and careful reading of the input format. Each of these is a pattern you will meet in interviews, and in the later modules of the course. Keep your solution, your tests and your notes on the tie rule. When you revisit array problems later, the same reasoning will apply.