АиАС 29.09.23

// ConsoleApplication1.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
#include <vector>
#include <string>

using namespace std;

template <typename T>
std::pair<T*, T*> minmax(T* first, T* last)
{
    int count = last - first;
    if (count == 0) return { nullptr,nullptr };
    T *min=first, *max=first;
    if(count%2==0)
        if (*first < *(first + 1))
            max = first + 1;
        else
            min = first + 1;
    for (T* cur = first + 2 - count % 2; cur != last; cur += 2)
    {
        if (*cur < *(cur + 1))
        {
            min = *cur < *min ? cur : min;
            max = *max < *(cur + 1) ? cur + 1 : max;
        }
        else
        {
            min = *(cur+1) < *min ? cur+1 : min;
            max = *max < *cur ? cur : max;
        }
    }
    return{ min,max };
}

template <typename T>
void minmax_sort(T* first, T* last)
{
    if (last - first <= 1) return;
    for (T* begin = first, *end = last - 1; end - begin > 0; begin++, end--)
    {
        auto [min, max] = minmax(begin, end + 1);
        std::swap(*begin, *min);
        if (max == begin)
            std::swap(*end, *min);
        else
            std::swap(*end, *max);
    }
}

pair<int, int> maximal_polyndromic_substring(const string& seq)
{
    if (seq == "")return{ 0,0 };
    for (int len = seq.length(); len > 0; --len)
    {
        for (size_t begin = 0; begin <= seq.length()-len; begin++)
        {
            int oddcount = 0;
            for (size_t i = 0; i < 26; i++)
                if (1 & std::count(std::begin(seq) + begin, std::begin(seq) + begin + len, 'a' + i))
                    ++oddcount;
            if (len % 2 && oddcount == 1 || len % 2 == 0 && oddcount == 0)
                return { begin,len };
        }
    }
    return { 1,1 };
}

int main()
{
    string s = "abracadabraaradakedavra";
    auto [begin, len] = maximal_polyndromic_substring(s);
    std::cout << s.substr(begin, len) << std::endl;
    int m[] = { 5,2,9,2,1,0,3,6 };
    minmax_sort(m, m + std::size(m));
    for (size_t i = 0; i < std::size(m); i++)
    {
        std::cout << m[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "Hello World!\n";
}

// Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
// Отладка программы: F5 или меню "Отладка" > "Запустить отладку"

// Советы по началу работы
//   1. В окне обозревателя решений можно добавлять файлы и управлять ими.
//   2. В окне Team Explorer можно подключиться к системе управления версиями.
//   3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
//   4. В окне "Список ошибок" можно просматривать ошибки.
//   5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
//   6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.