Monotone Minima
(convex/monge/monotone_minima.hpp)

• View this file on GitHub
• Last update: 2026-07-07 18:38:36+09:00
• Include: #include "convex/monge/monotone_minima.hpp"

Overview

The divide-and-conquer monotone-minima algorithm finds one optimum in every row when the leftmost optimal columns are known to be nondecreasing.

Its precondition is weaker and sometimes easier to establish than total monotonicity, although its asymptotic complexity is slightly worse than SMAWK. It is commonly used for divide-and-conquer DP optimization.

Interface

template <class Value>
std::vector<int> monotone_row_argmin(
    int row_count,
    int column_count,
    Value value
);

template <class Value>
std::vector<int> monotone_row_argmax(
    int row_count,
    int column_count,
    Value value
);

value(row, column) returns one implicit matrix entry. The result stores the optimal column for each row, choosing the leftmost optimum on ties.

Both functions also have convenience overloads accepting a rectangular std::vector<std::vector<T>>.

monotone_row_optima is the generic overload accepting a strict comparator.

If there are no columns, every answer is -1.

Requirements

The leftmost optimal columns under the chosen comparison must form a nondecreasing sequence. The implementation does not verify this condition.

Unlike SMAWK, this function does not require every submatrix to preserve monotonicity.

Complexity

For an H by W implicit matrix, the algorithm uses $O((H + W)\log H)$ callback evaluations in the general case and $O(H)$ additional memory including the result and recursion stack.

Example

#include "convex/monge/monotone_minima.hpp"
#include <vector>

int main() {
    std::vector<long long> previous = {0, 3, 4, 8, 10};
    auto transition = [&](int row, int column) {
        long long distance = row - column;
        return previous[column] + distance * distance;
    };

    auto opt = m1une::convex::monotone_row_argmin(5, 5, transition);
}

Required by

• Convex All (convex/all.hpp)
• Monge All (convex/monge/all.hpp)
• Divide-and-Conquer DP Optimization (convex/monge/divide_and_conquer_optimization.hpp)

Verified with

• verify/convex/monge/monge_algorithms.test.cpp
• verify/convex/monge/monge_dp_optimization.test.cpp

Code

#ifndef M1UNE_CONVEX_MONGE_MONOTONE_MINIMA_HPP
#define M1UNE_CONVEX_MONGE_MONOTONE_MINIMA_HPP 1

#include <cassert>
#include <functional>
#include <vector>

namespace m1une {
namespace convex {

namespace monotone_minima_detail {

template <class Value, class Compare>
void solve(int row_left, int row_right, int column_left, int column_right,
           const Value& value, const Compare& compare, std::vector<int>& answer) {
    if (row_left == row_right) return;
    int row = (row_left + row_right) / 2;
    int best = column_left;
    for (int column = column_left + 1; column < column_right; column++) {
        if (compare(value(row, column), value(row, best))) best = column;
    }
    answer[row] = best;
    solve(row_left, row, column_left, best + 1, value, compare, answer);
    solve(row + 1, row_right, best, column_right, value, compare, answer);
}

}  // namespace monotone_minima_detail

template <class Value, class Compare = std::less<>>
std::vector<int> monotone_row_optima(int row_count, int column_count, Value value,
                                     Compare compare = Compare()) {
    assert(row_count >= 0);
    assert(column_count >= 0);
    std::vector<int> answer(row_count, -1);
    if (row_count == 0 || column_count == 0) return answer;
    monotone_minima_detail::solve(0, row_count, 0, column_count, value, compare, answer);
    return answer;
}

template <class Value>
std::vector<int> monotone_row_argmin(int row_count, int column_count, Value value) {
    return monotone_row_optima(row_count, column_count, value, std::less<>());
}

template <class Value>
std::vector<int> monotone_row_argmax(int row_count, int column_count, Value value) {
    return monotone_row_optima(row_count, column_count, value, std::greater<>());
}

template <class T>
std::vector<int> monotone_row_argmin(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return monotone_row_argmin(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

template <class T>
std::vector<int> monotone_row_argmax(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return monotone_row_argmax(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

}  // namespace convex
}  // namespace m1une

#endif  // M1UNE_CONVEX_MONGE_MONOTONE_MINIMA_HPP

#line 1 "convex/monge/monotone_minima.hpp"



#include <cassert>
#include <functional>
#include <vector>

namespace m1une {
namespace convex {

namespace monotone_minima_detail {

template <class Value, class Compare>
void solve(int row_left, int row_right, int column_left, int column_right,
           const Value& value, const Compare& compare, std::vector<int>& answer) {
    if (row_left == row_right) return;
    int row = (row_left + row_right) / 2;
    int best = column_left;
    for (int column = column_left + 1; column < column_right; column++) {
        if (compare(value(row, column), value(row, best))) best = column;
    }
    answer[row] = best;
    solve(row_left, row, column_left, best + 1, value, compare, answer);
    solve(row + 1, row_right, best, column_right, value, compare, answer);
}

}  // namespace monotone_minima_detail

template <class Value, class Compare = std::less<>>
std::vector<int> monotone_row_optima(int row_count, int column_count, Value value,
                                     Compare compare = Compare()) {
    assert(row_count >= 0);
    assert(column_count >= 0);
    std::vector<int> answer(row_count, -1);
    if (row_count == 0 || column_count == 0) return answer;
    monotone_minima_detail::solve(0, row_count, 0, column_count, value, compare, answer);
    return answer;
}

template <class Value>
std::vector<int> monotone_row_argmin(int row_count, int column_count, Value value) {
    return monotone_row_optima(row_count, column_count, value, std::less<>());
}

template <class Value>
std::vector<int> monotone_row_argmax(int row_count, int column_count, Value value) {
    return monotone_row_optima(row_count, column_count, value, std::greater<>());
}

template <class T>
std::vector<int> monotone_row_argmin(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return monotone_row_argmin(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

template <class T>
std::vector<int> monotone_row_argmax(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return monotone_row_argmax(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

}  // namespace convex
}  // namespace m1une

Back to top page