Max Subarray Monoid
(monoid/max_subarray.hpp)

• View this file on GitHub
• Last update: 2026-07-21 20:17:47+09:00
• Include: #include "monoid/max_subarray.hpp"

Overview

A monoid for finding the maximum contiguous subarray sum within a range. The underlying state is m1une::monoid::SubarrayNode<T>, which holds 4 values:

1. sum: The sum of the entire segment.
2. pre: The maximum prefix sum.
3. suf: The maximum suffix sum.
4. opt: The maximum subarray sum inside the segment.

Initialization

To initialize a leaf node for a single value $x$, use the make(val, allow_empty) method.

• If empty subarrays are NOT allowed (Standard): Use make(x) or make(x, false). At least 1 element must be chosen.
• If empty subarrays ARE allowed (Max is bounded below by 0): Use make(x, true).

Example

#include "ds/segtree/segtree.hpp"
#include "monoid/max_subarray.hpp"
#include <iostream>
#include <vector>

using MaxSubM = m1une::monoid::MaxSubarray<long long>;

int main() {
    std::vector<long long> A = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int N = A.size();

    std::vector<MaxSubM::value_type> init_data(N);
    for (int i = 0; i < N; ++i) {
        // Standard initialization (At least 1 element must be chosen)
        init_data[i] = MaxSubM::make(A[i]);
    }

    m1une::ds::Segtree<MaxSubM> seg(init_data);

    // Max subarray sum in the whole array is 6 (from "4, -1, 2, 1")
    auto node = seg.prod(0, N);
    std::cout << "Max Subarray Sum: " << node.opt << "\n";

    return 0;
}

Interface and Complexity

This is a stateless algebra tag. Generic data structures use its public value_type, id(), and op(a, b) members. If the type also provides helpers such as make(...) or inv(x), they are described above or in the documented properties.

Each static operation runs in the cost of the underlying operation shown in the properties. Scalar monoids are $O(1)$; monoids whose value_type stores several items, permutations, or matrices scale with that stored size.

Depends on

• Min Subarray Monoid (monoid/min_subarray.hpp)

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_MAX_SUBARRAY_HPP
#define M1UNE_MONOID_MAX_SUBARRAY_HPP 1

#include <functional>
#include <limits>

#include "min_subarray.hpp"

namespace m1une {
namespace monoid {

// Monoid for finding the maximum subarray sum in a range.
// Defined as a type alias of MinSubarray using std::greater.
template <typename T, T Id = std::numeric_limits<T>::lowest() / 2>
using MaxSubarray = MinSubarray<T, Id, std::greater<T>>;

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_MAX_SUBARRAY_HPP

#line 1 "monoid/max_subarray.hpp"



#include <functional>
#include <limits>

#line 1 "monoid/min_subarray.hpp"



#line 6 "monoid/min_subarray.hpp"

namespace m1une {
namespace monoid {

// Node for managing the optimal subarray sum.
template <typename T>
struct SubarrayNode {
    T sum;
    T pre;
    T suf;
    T opt;  // Holds the optimal value (e.g., min or max)
};

// Monoid for finding the minimum subarray sum in a range.
// Uses a comparison functor (Compare) to determine the optimal value.
// Can be reused for maximum subarray sum by changing the Compare functor.
template <typename T, T Id = std::numeric_limits<T>::max() / 2, typename Compare = std::less<T>>
struct MinSubarray {
    using value_type = SubarrayNode<T>;
    static constexpr bool commutative = false;

    // The identity element contains values that do not affect the result.
    static constexpr value_type id() {
        return {T(0), Id, Id, Id};
    }

    // Merges two subarray nodes.
    static constexpr value_type op(const value_type& a, const value_type& b) {
        if (a.opt == Id) return b;
        if (b.opt == Id) return a;

        // Lambda to select the optimal value according to the comparison functor.
        auto get_opt = [](const T& x, const T& y) { return Compare()(x, y) ? x : y; };

        return {a.sum + b.sum, get_opt(a.pre, a.sum + b.pre), get_opt(b.suf, a.suf + b.sum),
                get_opt(get_opt(a.opt, b.opt), a.suf + b.pre)};
    }

    // Helper to securely create a leaf node from a single value.
    // Set `allow_empty = true` if empty subarrays (sum = 0) are valid answers.
    static constexpr value_type make(const T& val, bool allow_empty = false) {
        if (allow_empty) {
            T opt_val = Compare()(val, T(0)) ? val : T(0);
            return {val, opt_val, opt_val, opt_val};
        }
        return {val, val, val, val};
    }
};

}  // namespace monoid
}  // namespace m1une


#line 8 "monoid/max_subarray.hpp"

namespace m1une {
namespace monoid {

// Monoid for finding the maximum subarray sum in a range.
// Defined as a type alias of MinSubarray using std::greater.
template <typename T, T Id = std::numeric_limits<T>::lowest() / 2>
using MaxSubarray = MinSubarray<T, Id, std::greater<T>>;

}  // namespace monoid
}  // namespace m1une

Back to top page