Non-Adjacent Selection Sums
(algo/sequence/non_adjacent_selection.hpp)

• View this file on GitHub
• Last update: 2026-07-18 18:19:15+09:00
• Include: #include "algo/sequence/non_adjacent_selection.hpp"

Overview

For every feasible positive count, this header finds the optimum sum obtained by selecting exactly that many values from an array while never selecting two adjacent indices.

The public namespace is m1une::algo.

Functions

Function	Description	Complexity
std::vector<T> maximum_non_adjacent_selection_sums(const std::vector<T>& values)	Returns the maximum exact-count sums.	$O(N \log N)$ time and $O(N)$ memory
std::vector<T> minimum_non_adjacent_selection_sums(const std::vector<T>& values)	Returns the minimum exact-count sums.	$O(N \log N)$ time and $O(N)$ memory

Both functions return a vector of length $\lceil N/2 \rceil$. Entry k - 1 is the optimum sum when exactly k values are selected, for $1 \leq k \leq \lceil N/2 \rceil$. An empty input returns an empty vector.

T must be default-constructible, copyable, totally ordered, and support addition, subtraction, and +=. Every input sum and intermediate contraction value must fit in T.

Algorithm

Treat each array position as an edge of a path. A set of non-adjacent positions is then a matching. The algorithm repeatedly extracts the best edge weight from a priority queue. If both neighboring edges exist, it contracts the three weights left, current, and right into

\[\mathrm{left} + \mathrm{right} - \mathrm{current}.\]

This contraction preserves the remaining exact-cardinality matching optima. Each extracted weight is the next marginal optimum, so its prefix sums are the answers for all cardinalities. Boundary extractions simply remove the selected edge and its one neighbor.

Example

#include "algo/sequence/non_adjacent_selection.hpp"

#include <iostream>
#include <vector>

int main() {
    std::vector<long long> values = {4, 1, 7, 3};

    std::vector<long long> maximum =
        m1une::algo::maximum_non_adjacent_selection_sums(values);
    std::vector<long long> minimum =
        m1une::algo::minimum_non_adjacent_selection_sums(values);

    for (long long value : maximum) std::cout << value << ' ';
    std::cout << '\n';  // 7 11

    for (long long value : minimum) std::cout << value << ' ';
    std::cout << '\n';  // 1 4
}

Required by

• Algorithms All (algo/all.hpp)
• Sequence Algorithms All (algo/sequence/all.hpp)

Verified with

• verify/algo/sequence/non_adjacent_selection.test.cpp

Code

#ifndef M1UNE_ALGO_SEQUENCE_NON_ADJACENT_SELECTION_HPP
#define M1UNE_ALGO_SEQUENCE_NON_ADJACENT_SELECTION_HPP 1

#include <functional>
#include <queue>
#include <vector>

namespace m1une {
namespace algo {

namespace detail {

template <typename T>
struct NonAdjacentSelectionEntry {
    T value;
    int index;
};

template <typename T, typename Better>
struct NonAdjacentSelectionCompare {
    Better better;

    bool operator()(
        const NonAdjacentSelectionEntry<T>& lhs,
        const NonAdjacentSelectionEntry<T>& rhs
    ) const {
        if (better(lhs.value, rhs.value)) return false;
        if (better(rhs.value, lhs.value)) return true;
        return lhs.index > rhs.index;
    }
};

template <typename T, typename Better>
std::vector<T> non_adjacent_selection_sums(const std::vector<T>& values, Better better) {
    const int n = int(values.size());
    std::vector<T> weight = values;
    std::vector<int> left(n), right(n);
    std::vector<char> alive(n, true);
    for (int i = 0; i < n; ++i) {
        left[i] = i - 1;
        right[i] = (i + 1 == n ? -1 : i + 1);
    }

    using Entry = NonAdjacentSelectionEntry<T>;
    using Compare = NonAdjacentSelectionCompare<T, Better>;
    std::priority_queue<Entry, std::vector<Entry>, Compare> heap(Compare{better});
    for (int i = 0; i < n; ++i) heap.push(Entry{weight[i], i});

    std::vector<T> result;
    result.reserve((n + 1) / 2);
    T sum{};
    while (int(result.size()) < (n + 1) / 2) {
        while (!alive[heap.top().index]) heap.pop();
        const int current = heap.top().index;
        heap.pop();

        sum += weight[current];
        result.push_back(sum);

        const int l = left[current];
        const int r = right[current];
        if (l != -1 && r != -1) {
            weight[current] = weight[l] + weight[r] - weight[current];

            const int ll = left[l];
            const int rr = right[r];
            alive[l] = false;
            alive[r] = false;
            left[current] = ll;
            right[current] = rr;
            if (ll != -1) right[ll] = current;
            if (rr != -1) left[rr] = current;
            heap.push(Entry{weight[current], current});
        } else {
            const int ll = (l == -1 ? -1 : left[l]);
            const int rr = (r == -1 ? -1 : right[r]);
            alive[current] = false;
            if (l != -1) alive[l] = false;
            if (r != -1) alive[r] = false;
            if (ll != -1) right[ll] = rr;
            if (rr != -1) left[rr] = ll;
        }
    }
    return result;
}

}  // namespace detail

// Entry k - 1 is the maximum sum obtained by selecting exactly k values, with
// no two selected indices adjacent.
template <typename T>
std::vector<T> maximum_non_adjacent_selection_sums(const std::vector<T>& values) {
    return detail::non_adjacent_selection_sums(values, std::greater<T>{});
}

// Entry k - 1 is the minimum sum obtained by selecting exactly k values, with
// no two selected indices adjacent.
template <typename T>
std::vector<T> minimum_non_adjacent_selection_sums(const std::vector<T>& values) {
    return detail::non_adjacent_selection_sums(values, std::less<T>{});
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_SEQUENCE_NON_ADJACENT_SELECTION_HPP

#line 1 "algo/sequence/non_adjacent_selection.hpp"



#include <functional>
#include <queue>
#include <vector>

namespace m1une {
namespace algo {

namespace detail {

template <typename T>
struct NonAdjacentSelectionEntry {
    T value;
    int index;
};

template <typename T, typename Better>
struct NonAdjacentSelectionCompare {
    Better better;

    bool operator()(
        const NonAdjacentSelectionEntry<T>& lhs,
        const NonAdjacentSelectionEntry<T>& rhs
    ) const {
        if (better(lhs.value, rhs.value)) return false;
        if (better(rhs.value, lhs.value)) return true;
        return lhs.index > rhs.index;
    }
};

template <typename T, typename Better>
std::vector<T> non_adjacent_selection_sums(const std::vector<T>& values, Better better) {
    const int n = int(values.size());
    std::vector<T> weight = values;
    std::vector<int> left(n), right(n);
    std::vector<char> alive(n, true);
    for (int i = 0; i < n; ++i) {
        left[i] = i - 1;
        right[i] = (i + 1 == n ? -1 : i + 1);
    }

    using Entry = NonAdjacentSelectionEntry<T>;
    using Compare = NonAdjacentSelectionCompare<T, Better>;
    std::priority_queue<Entry, std::vector<Entry>, Compare> heap(Compare{better});
    for (int i = 0; i < n; ++i) heap.push(Entry{weight[i], i});

    std::vector<T> result;
    result.reserve((n + 1) / 2);
    T sum{};
    while (int(result.size()) < (n + 1) / 2) {
        while (!alive[heap.top().index]) heap.pop();
        const int current = heap.top().index;
        heap.pop();

        sum += weight[current];
        result.push_back(sum);

        const int l = left[current];
        const int r = right[current];
        if (l != -1 && r != -1) {
            weight[current] = weight[l] + weight[r] - weight[current];

            const int ll = left[l];
            const int rr = right[r];
            alive[l] = false;
            alive[r] = false;
            left[current] = ll;
            right[current] = rr;
            if (ll != -1) right[ll] = current;
            if (rr != -1) left[rr] = current;
            heap.push(Entry{weight[current], current});
        } else {
            const int ll = (l == -1 ? -1 : left[l]);
            const int rr = (r == -1 ? -1 : right[r]);
            alive[current] = false;
            if (l != -1) alive[l] = false;
            if (r != -1) alive[r] = false;
            if (ll != -1) right[ll] = rr;
            if (rr != -1) left[rr] = ll;
        }
    }
    return result;
}

}  // namespace detail

// Entry k - 1 is the maximum sum obtained by selecting exactly k values, with
// no two selected indices adjacent.
template <typename T>
std::vector<T> maximum_non_adjacent_selection_sums(const std::vector<T>& values) {
    return detail::non_adjacent_selection_sums(values, std::greater<T>{});
}

// Entry k - 1 is the minimum sum obtained by selecting exactly k values, with
// no two selected indices adjacent.
template <typename T>
std::vector<T> minimum_non_adjacent_selection_sums(const std::vector<T>& values) {
    return detail::non_adjacent_selection_sums(values, std::less<T>{});
}

}  // namespace algo
}  // namespace m1une

Back to top page