Maximum subarray with node merging

Why this matters

A stock price changes every day. The daily change is a number that can be positive or negative. A useful question is: over which run of consecutive days did the price rise the most? A run of consecutive values is called a subarray. Its sum is the total of the values in that run. The question asks for the largest such sum.

For one array, a single pass solves this. That pass is called Kadane's algorithm, and it takes time proportional to the array length. The harder version asks the same question again and again, for many different ranges, while single values in the array also change. A segment tree can answer a range question in time proportional to the logarithm of the array length. A logarithm here means roughly how many times you can cut the length in half before reaching 1. That speed only works if two neighbouring nodes can be combined quickly.

This lesson builds a segment tree that answers "what is the largest subarray sum inside positions l to r?" The key idea is that each node stores four numbers instead of one, and two nodes can be merged with a fixed amount of work. Simpler segment trees store one number per node. This lesson needs four because a subarray can start in one half of a range and end in the other half.

You need to know what a segment tree is and how a recursive function splits a range in two. Earlier lessons in this module cover both. The code uses std::optional, a standard C++ type that holds either a value or nothing. Read std::optional<Info> as "an Info, or nothing at all".

The problem with one number per node

Start with the simplest idea. Each node stores the best subarray sum inside its range. Look at this array:

positions:  0   1   2   3   4
values:     2  -5   3   4  -1

The left half is positions 0 and 1, with values 2 and -5. Its best subarray sum is 2, from position 0 alone. The right half is positions 2 to 4, with values 3, 4 and -1. Its best sum is 7, from positions 2 and 3 together.

The best sum of the whole array is also 7, and here it comes from the right half. Now change the values to 3, -1, 4. The left half 3, -1 has best sum 3. The right half 4 has best sum 4. Taking the larger, 4, is wrong. The subarray 3, -1, 4 covers both halves and has sum 6. A subarray that crosses the middle of the range is not inside either half, so storing only the two best values loses it.

To merge two halves correctly, the parent node must know how much the left half is worth when it is taken from its right end, and how much the right half is worth when it is taken from its left end. These are two more numbers.

Four numbers per node

Every node stores four values for the range it covers.

• total: the sum of every value in the range.
• prefix: the best sum of a non-empty subarray that starts at the left end of the range. A prefix is the first part of something. In 3, -1, 4 the prefix choices are 3, 3 + -1 = 2 and 2 + 4 = 6. The best is 6.
• suffix: the best sum of a non-empty subarray that ends at the right end of the range. A suffix is the last part. For 3, -1, 4 the suffix choices are 4, -1 + 4 = 3 and 3 + -1 + 4 = 6. The best is 6.
• best: the best sum of a non-empty subarray that lies anywhere in the range.

The word "non-empty" matters. A subarray must contain at least one value. This rule is what makes an all-negative range return a negative answer. If an empty subarray were allowed, the answer would always be at least 0.

For the range 3, -1, 4 the four values happen to be the same: total 6, prefix 6, suffix 6, best 6. The worked examples below use ranges where they differ.

Leaf nodes

A leaf is a node that covers exactly one position. A single value v has one choice of subarray, which is v itself. So all four numbers are v:

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

The struct fields are in the order total, prefix, suffix, best. The brace list fills them in that order.

Merging two nodes

Suppose a node has a left child A and a right child B. The left child covers the positions before the right child. Here is how the parent's four numbers come from A and B.

• total: A.total + B.total. The sum of everything is the sum of both halves.
• prefix: the best prefix of the whole range is either the best prefix of A, or all of A followed by the best prefix of B. So max(A.prefix, A.total + B.prefix).
• suffix: by the same reasoning from the other side, max(B.suffix, B.total + A.suffix).
• best: the best subarray is inside A, or inside B, or it crosses the middle. A subarray that crosses the middle is a suffix of A followed by a prefix of B. So max(A.best, B.best, A.suffix + B.prefix).

Each formula uses only the four numbers of the two children. The merge does a fixed number of additions and comparisons, so it takes constant time. Constant time means the amount of work does not grow with the size of the ranges.

Here is a worked merge. The left child covers 2, -5 and the right child covers 3, 4, -1.

The left child's four numbers come from merging the leaves 2 and -5:

• total: 2 + -5 = -3
• prefix: max(2, 2 + -5) = max(2, -3) = 2
• suffix: max(-5, -5 + 2) = max(-5, -3) = -3
• best: max(2, -5, 2 + -5) = max(2, -5, -3) = 2

The right child's four numbers come from merging 3 and 4, then merging that with -1. The merge of 3 and 4 gives total 7, prefix 7, suffix 7 and best 7. Merging with -1 gives:

• total: 7 + -1 = 6
• prefix: max(7, 7 + -1) = 7
• suffix: max(-1, -1 + 7) = 6
• best: max(7, -1, 7 + -1) = 7

Now merge the two children, with A being the left child and B the right child:

• total: -3 + 6 = 3
• prefix: max(2, -3 + 7) = max(2, 4) = 4. The best prefix of the whole range is 2, -5, 3, 4, whose sum is 4.
• suffix: max(6, 6 + -3) = max(6, 3) = 6
• best: max(2, 7, -3 + 7) = max(2, 7, 4) = 7

The whole range has best 7. That comes from the right child alone. The crossing candidate is A.suffix + B.prefix = -3 + 7 = 4, which is smaller, so it does not win here. The merge still checks it, because in other arrays the crossing subarray is the winner.

Building the tree

A segment tree stores one node per range. The root covers the whole array. Each node that covers more than one position splits its range at the middle, and its two children cover the two halves. The tree is stored in a std::vector. The root is at index 1, and the children of node k are at 2k and 2k + 1. Four slots per array position is always enough for this layout, so the vector is sized 4 * n.

The code below builds the tree, answers queries and updates single values. It also compares the answers with a slow brute-force check on random arrays. A brute-force check tries every possibility, which is slow but easy to trust. Save the code as msub.cpp and compile it with:

g++ -std=c++20 -Wall -Wextra -o msub msub.cpp
./msub

#include <algorithm>
#include <iostream>
#include <optional>
#include <random>
#include <vector>
 
struct Info {
    long long total;   // sum of every value in the piece
    long long prefix;  // best sum of a non-empty prefix
    long long suffix;  // best sum of a non-empty suffix
    long long best;    // best sum of a non-empty contiguous part
};
 
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}),
    };
}
 
std::optional<Info> combine(const std::optional<Info>& a, const std::optional<Info>& b) {
    if (!a) return b;
    if (!b) return a;
    return merge(*a, *b);
}
 
class SegTree {
public:
    explicit SegTree(const std::vector<long long>& a) : n_(static_cast<int>(a.size())), t_(4 * a.size()) {
        build(1, 0, n_ - 1, a);
    }
 
    void set(int pos, long long v) { set(1, 0, n_ - 1, pos, v); }
 
    std::optional<Info> query(int l, int r) const { return query(1, 0, n_ - 1, l, r); }
 
private:
    void build(int node, int lo, int hi, const std::vector<long long>& a) {
        if (lo == hi) {
            t_[node] = leaf(a[lo]);
            return;
        }
        int mid = lo + (hi - lo) / 2;
        build(2 * node, lo, mid, a);
        build(2 * node + 1, mid + 1, hi, a);
        t_[node] = merge(t_[2 * node], t_[2 * node + 1]);
    }
 
    void set(int node, int lo, int hi, int pos, long long v) {
        if (lo == hi) {
            t_[node] = leaf(v);
            return;
        }
        int mid = lo + (hi - lo) / 2;
        if (pos <= mid) {
            set(2 * node, lo, mid, pos, v);
        } else {
            set(2 * node + 1, mid + 1, hi, pos, v);
        }
        t_[node] = merge(t_[2 * node], t_[2 * node + 1]);
    }
 
    std::optional<Info> query(int node, int lo, int hi, int l, int r) const {
        if (r < lo || hi < l) return std::nullopt;
        if (l <= lo && hi <= r) return t_[node];
        int mid = lo + (hi - lo) / 2;
        return combine(query(2 * node, lo, mid, l, r), query(2 * node + 1, mid + 1, hi, l, r));
    }
 
    int n_;
    std::vector<Info> t_;
};
 
long long brute(const std::vector<long long>& a, int l, int r) {
    long long best = a[l];
    for (int i = l; i <= r; ++i) {
        long long s = 0;
        for (int j = i; j <= r; ++j) {
            s += a[j];
            best = std::max(best, s);
        }
    }
    return best;
}
 
int main() {
    std::vector<long long> a{2, -5, 3, 4, -1};
    SegTree st(a);
    std::cout << "whole array best: " << st.query(0, 4)->best << '\n';
    std::cout << "[0,1] best:       " << st.query(0, 1)->best << '\n';
    std::cout << "[1,4] best:       " << st.query(1, 4)->best << '\n';
    std::cout << "[1,1] best:       " << st.query(1, 1)->best << '\n';
 
    SegTree neg({-3, -1, -4});
    std::cout << "all negative [-3,-1,-4] best: " << neg.query(0, 2)->best << '\n';
 
    st.set(1, 10);
    std::cout << "after set(1, 10), whole best: " << st.query(0, 4)->best << '\n';
 
    std::mt19937 rng(12345);
    std::uniform_int_distribution<int> len(1, 12), val(-20, 20);
    int checks = 0;
    for (int trial = 0; trial < 300; ++trial) {
        int n = len(rng);
        std::vector<long long> b(n);
        for (auto& x : b) x = val(rng);
        SegTree t(b);
        for (int q = 0; q < 30; ++q) {
            int l = std::uniform_int_distribution<int>(0, n - 1)(rng);
            int r = std::uniform_int_distribution<int>(l, n - 1)(rng);
            if (t.query(l, r)->best != brute(b, l, r)) {
                std::cout << "MISMATCH\n";
                return 1;
            }
            ++checks;
            if (q % 7 == 0) {
                int p = std::uniform_int_distribution<int>(0, n - 1)(rng);
                long long v = val(rng);
                b[p] = v;
                t.set(p, v);
            }
        }
    }
    std::cout << "random checks passed: " << checks << '\n';
}

The program prints:

whole array best: 7
[0,1] best:       2
[1,4] best:       7
[1,1] best:       -5
all negative [-3,-1,-4] best: -1
after set(1, 10), whole best: 19
random checks passed: 9000

The brute-force function tries every subarray, which takes time proportional to the square of the range length. The 9000 random queries all agree with it, including queries made after single values change.

Answering a range query

A query for the range l to r walks down the tree the same way as a range sum query. A node that lies completely inside the range returns its stored four numbers. A node that lies completely outside returns nothing. A node that is partly inside asks both children and combines their answers.

The function returns std::optional<Info> rather than Info. The reason is the empty answer. A range that covers no positions has no subarray, so there is no best value to return. A zero-filled Info would claim that the best subarray has sum 0, and that is wrong for an all-negative range. Returning std::nullopt says "nothing here", and combine skips the missing side.

When a query covers two or more pieces, combine merges their answers in the same order as the positions. The left piece is always passed first, so the merge sees the left piece as a and the right piece as b. Swapping them gives wrong answers.

A query visits at most about four nodes on each level of the tree. The number of levels is about the logarithm of the array length, so one query takes time proportional to the logarithm of n.

Worked example 1: the best run crosses the middle

Use the array 3, -1, 4. The answer is 6, from the whole array. Each half alone is wrong:

• The left half 3, -1 has best 3.
• The right half 4 has best 4.
• The crossing subarray 3, -1, 4 has sum 6.

Build the tree by hand. The root covers positions 0 to 2. Its left child covers positions 0 to 1, and its right child covers position 2.

The left child merges the leaves 3 and -1:

• total 2, prefix max(3, 2) = 3, suffix max(-1, -1 + 3) = 2, best max(3, -1, 3 + -1) = 3

The root merges that with the leaf 4:

• total 2 + 4 = 6
• prefix max(3, 2 + 4) = 6
• suffix max(4, 4 + 2) = 6
• best max(3, 4, 2 + 4) = 6

The crossing term A.suffix + B.prefix = 2 + 4 gives the answer 6. Without that term, the best would be 4.

Worked example 2: a query on a middle range

Take the array below. Its best subarray is 4, -1, 2, 1, with sum 6.

positions:  0   1   2   3   4   5   6   7   8
values:    -2   1  -3   4  -1   2   1  -5   4

The whole-array query gives 6. Now query positions 4 to 8, which hold -1, 2, 1, -5, 4. The subarrays and their sums are -1, 2, 1 with sum 2, 2, 1 with sum 3, 4 alone with sum 4, and the rest are smaller. The best is 4, from the last value alone.

The tree does not mix in the values at positions 0 to 3. It only uses nodes that lie completely inside positions 4 to 8, and merges their four numbers. A node that covers positions 2 to 5, for example, is only used if it lies completely inside the query range. Otherwise the query splits it and uses its children.

Worked example 3: all values negative

Take -3, -1, -4. Without the non-empty rule, the answer would be 0, because the empty subarray has sum 0. With the rule, the best is the largest single value, which is -1.

The leaf for -1 has best -1. The merge keeps max(A.best, B.best, A.suffix + B.prefix). Adding two negative numbers gives something more negative, so the single value wins. The program in the code section prints -1 for this case.

Common mistakes

Forgetting the crossing candidate. If merge returns max(a.best, b.best) and drops a.suffix + b.prefix, the array 3, -1, 4 gives 4 instead of 6. Worked example 1 shows the crossing sum that is missing.

Mixing types in std::max. The std::max function with a brace list needs every value to have the same type. The code uses long long everywhere. If one value is an int, the compiler stops. Here is a real error from g++ 15 for a call that mixes long long and int. The output continues with notes that are not shown here:

err.cpp:5:37: error: no matching function for call to ‘max(<brace-enclosed initializer list>)’
    5 |     return static_cast<int>(std::max({a, b, c}));

The fix is to make every value the same type, for example by writing static_cast<long long>(c), or by declaring c as long long from the start.

Using a zero Info as the empty answer. A zero Info has best 0, which is larger than any negative answer. A query that combines it with a node of all negative values returns 0. The std::optional return type prevents this. Lesson 15 of this module shows how a wrong neutral value breaks a minimum query in a similar way.

Swapping the order in combine. merge is not symmetric. Merging 4 on the left with 3, -1 on the right gives best max(4, 3, 4 + 3) = 7 for the array 3, -1, 4. The number 7 is not a real subarray sum for that array, because the values are in the order 3, -1, 4. The left piece must always be the piece with the smaller positions.

Splitting ranges differently in different functions. build, set and query must all split a range at the same point. If build splits at one point and query splits at another, a query reads a node that covers different positions from the ones it was built from. The answers are then wrong, and often only on some ranges. The code uses mid = lo + (hi - lo) / 2 in every function for this reason.

Practice

Exercise 1: merge two leaves by hand

Find the four numbers for the array 1, -2, 3. Merge 1 and -2 first, then merge the result with 3. Report the best value. Check it by listing every subarray with its sum.

Show the answer

Merging 1 and -2 gives total -1, prefix max(1, 1 + -2) = 1, suffix max(-2, -2 + 1) = -1, and best max(1, -2, 1 + -2) = 1. Merging that with 3 gives total 2, prefix max(1, -1 + 3) = 2, suffix max(3, 3 + -1) = 3, and best max(1, 3, -1 + 3) = 3. The best value is 3. The other subarrays have sums 1, -1, 2, -2 and 1, so none is larger.

Exercise 2: a query on the first four positions

For the array -2, 1, -3, 4, -1, 2, 1, -5, 4, what does a query on positions 0 to 3 return? Work it out by listing the subarrays of -2, 1, -3, 4.

Show the answer

The values are -2, 1, -3, 4. The subarray 4 alone has sum 4. The subarray 1, -3, 4 has sum 2, and -2, 1, -3, 4 has sum 0. No other subarray is larger than 4. The query returns best 4.

Exercise 3: why the prefix formula needs the total

The prefix formula is max(A.prefix, A.total + B.prefix). Explain what goes wrong if the code uses max(A.prefix, B.prefix) instead. Use the left child 2, -5 and the right child 3.

Show the answer

The correct whole prefix is 2. The prefixes that start at position 0 are 2 with sum 2, 2, -5 with sum -3, and 2, -5, 3 with sum 0. The wrong formula gives max(A.prefix, B.prefix) = max(2, 3) = 3. The value 3 is the prefix of the right child, 3 alone, but that piece does not start at position 0. The total of the left child, -3 here, must be added before the right child's prefix, because a prefix of the whole range has to pass through all of the left child.

Exercise 4: change the merge to find the smallest subarray sum

Change merge so that the tree answers "what is the smallest sum of a non-empty subarray?" Keep the same four fields and the same leaf function. Write the new merge.

Show the answer

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

Each max becomes min. The reasons are the same as before. The smallest prefix either stops inside the left child or runs through all of it, and the smallest crossing subarray is a suffix of the left child plus a prefix of the right child.

Exercise 5: why the query returns an optional

A query on a range that has no positions has no answer. Suppose the code returned a zero-filled Info for a node that lies outside the range. Give one example array and one query where the answer becomes wrong.

Show the answer

Take the array -3, -1, -4 and the query on positions 1 to 1, which holds only -1. Suppose the query also visits a node that lies outside the range and returns a zero Info. Merging that zero Info with the leaf for -1 gives best max(0, -1, 0 + -1) = 0. The correct answer is -1. With std::optional, the outside node returns std::nullopt, and combine returns the inside answer unchanged.

Summary

• Each node stores total, prefix, suffix and best. These four numbers are enough to merge two children.
• A merge uses max and + on the children's numbers, so it takes constant time.
• The best value of a parent is the largest of the left best, the right best, and the left suffix plus the right prefix.
• Queries return std::optional<Info>, because a range with no positions has no answer.
• A brute-force check on random arrays is a fast way to test a merge formula.