prefix_suffix.hpp

Go to the documentation of this file.

#ifndef PREFIX_SUFFIX_H
#define PREFIX_SUFFIX_H
 
#include <concepts>
#include <vector>
#include <algorithm>
#include <numeric>
 
namespace hsc_snippets
{
    template<std::integral T>
    static std::vector<T> getPrefixMax(const std::vector<T> &v) {
        if (v.empty()) {
            return {};
        }
        std::vector<T> prefixMax(v.size());
        prefixMax[0] = v[0];
        for (size_t i = 1; i < v.size(); ++i) {
            prefixMax[i] = std::max(prefixMax[i - 1], v[i]);
        }
        return prefixMax;
    }
 
    template<std::integral T>
    static std::vector<T> getSuffixMax(const std::vector<T> &v) {
        if (v.empty()) {
            return {};
        }
        std::vector<T> suffixMax(v.size());
        size_t n = v.size();
        suffixMax[n - 1] = v[n - 1];
        for (size_t i = n - 2; i < n; --i) {
            suffixMax[i] = std::max(suffixMax[i + 1], v[i]);
        }
        return suffixMax;
    }
 
    template<std::integral T>
    static std::vector<T> getPrefixMin(const std::vector<T> &v) {
        if (v.empty()) {
            return {};
        }
        std::vector<T> prefixMin(v.size());
        prefixMin[0] = v[0];
        for (size_t i = 1; i < v.size(); ++i) {
            prefixMin[i] = std::min(prefixMin[i - 1], v[i]);
        }
        return prefixMin;
    }
 
    template<std::integral T>
    static std::vector<T> getSuffixMin(const std::vector<T> &v) {
        if (v.empty()) {
            return {};
        }
        std::vector<T> suffixMin(v.size());
        size_t n = v.size();
        suffixMin[n - 1] = v[n - 1];
        for (size_t i = n - 2; i < n; --i) {
            suffixMin[i] = std::min(suffixMin[i + 1], v[i]);
        }
        return suffixMin;
    }
 
    template<std::integral T>
    static std::vector<T> getPrefixSum(const std::vector<T> &v) {
        if (v.empty()) {
            return {};
        }
        std::vector<T> prefixSum(v.size());
        std::partial_sum(v.begin(), v.end(), prefixSum.begin());
        return prefixSum;
    }
 
    template<std::integral T>
    static std::vector<T> getSuffixSum(const std::vector<T> &v) {
        if (v.empty()) {
            return {};
        }
        std::vector<T> suffixSum(v.size());
        size_t n = v.size();
        std::partial_sum(v.rbegin(), v.rend(), suffixSum.rbegin());
        return suffixSum;
    }
}
 
#endif // PREFIX_SUFFIX_H