library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: Monoid: Max Subarray Sum
(algebra/monoid_max_subarray_sum.hpp)

概要

使い方

Verified with

Code

#pragma once
#include <algorithm>
#include <limits>
template <class T>
struct monoid_max_subarray_sum {
    struct S {
        T sum, max_prefix, max_suffix, max_subarray;
    };
    static S op(S a, S b) {
        if (a.max_subarray == ninf) return b;
        if (b.max_subarray == ninf) return a;
        return {a.sum + b.sum, std::max(a.max_prefix, a.sum + b.max_prefix), std::max(b.max_suffix, a.max_suffix + b.sum),
                std::max({a.max_subarray, b.max_subarray, a.max_suffix + b.max_prefix})};
    }
    static S e() {
        return {T(0), ninf, ninf, ninf};
    }
    static S from(T v) {
        return {v, v, v, v};
    }

private:
    static constexpr T ninf = std::numeric_limits<T>::lowest();
};
#line 2 "algebra/monoid_max_subarray_sum.hpp"
#include <algorithm>
#include <limits>
template <class T>
struct monoid_max_subarray_sum {
    struct S {
        T sum, max_prefix, max_suffix, max_subarray;
    };
    static S op(S a, S b) {
        if (a.max_subarray == ninf) return b;
        if (b.max_subarray == ninf) return a;
        return {a.sum + b.sum, std::max(a.max_prefix, a.sum + b.max_prefix), std::max(b.max_suffix, a.max_suffix + b.sum),
                std::max({a.max_subarray, b.max_subarray, a.max_suffix + b.max_prefix})};
    }
    static S e() {
        return {T(0), ninf, ninf, ninf};
    }
    static S from(T v) {
        return {v, v, v, v};
    }

private:
    static constexpr T ninf = std::numeric_limits<T>::lowest();
};
Back to top page