Найти в массиве длину максимальной подпоследовательности одинаковых элементов

[ZenettanyВерифицированный профиль]

Нахождение максимальной подпоследовательности одинаковых элементов​

Как следует из названия темы, изначально в задании требуется в массиве целых чисел типа int найти длину максимальной подпоследовательности одинаковых (равных) чисел.

Например, если имеется следующий массив:

int a[] = { 2, 4, 4, 1, 3, 4, 4, 4, 4, 4, 6, 6, 6 };

то максимальная подпоследовательность равных элементов это { 4, 4, 4, 4, 4 }, и ее длина равна 5.

Эта тема создана мною как повод обратить внимание программистов, особенно начинающих, на то, что когда решаете даже очень простую задачу, старайтесь ее обобщить и найти ее применение в более широких контекстах. Это сделает реализацию соответствующей задачи более универсальной, позволит избежать дублирования и разбухания кода, расширит ваш кругозор и познания в программировании и алгоритмах.

Но вернемся к исходной задаче.

Начнем с объявления соответствующей функции. Назовем функцию, к примеру, max_subsequence_length. Вот ее объявление:

size_t max_subsequence_length( const int a[], size_t n );

Важно обратить внимание, что первый параметр должен быть объявлен с квалификатором const, так как массив не изменяется внутри функции. Второй параметр и возвращаемое значение должны иметь беззнаковый тип size_t. Некоторые особенно малоквалифицированные программисты в качестве типа размера массива используют знаковый тип int. Во-первых, размер массива не может быть отрицательным числом. Во-вторых, диапазон положительных значений типа int недостаточен, чтобы указать размер любого массива. И, в-третьих, все стандартные C функции объявляют соответствующие параметры, задающие размеры массивов, с типом size_t.

Опредение функции может выглядеть так:

size_t max_subsequence_length( const int a[], size_t n ) 
{ 
    size_t longest_length = 0; 
     
    for ( size_t i = 0; i++ < n; ) 
    { 
        size_t j = i - 1; 
         
        while ( i < n && a[i-1] == a[i] ) ++i; 
         
        if ( longest_length < i - j ) longest_length = i - j; 
    } 
     
    return longest_length; 
}

Ниже представлена демонстрационная программа:

#include <stdio.h> 
 
size_t max_subsequence_length( const int a[], size_t n ) 
{ 
    size_t longest_length = 0; 
     
    for ( size_t i = 0; i++ < n; ) 
    { 
        size_t j = i - 1; 
         
        while ( i < n && a[i-1] == a[i] ) ++i; 
         
        if ( longest_length < i - j ) longest_length = i - j; 
    } 
     
    return longest_length; 
} 
 
int main(void)  
{ 
    int a[] = { 2, 4, 4, 1, 3, 4, 4, 4, 4, 4, 6, 6, 6 }; 
    size_t n = sizeof( a ) / sizeof( *a ); 
     
    printf( "The longest length of duplicated elements is %zu.\n", max_subsequence_length( a, n ) ); 
}

Вывод программы на консоль:

The longest length of duplicated elements is 5.

Альтернативно функция может быть определена также следующим образом:

size_t max_subsequence_length( const int a[], size_t n ) 
{ 
    size_t longest_length = n != 0; 
 
    for (size_t i = 1, current_length = 1; i < n; i++) 
    { 
        if (a[i - 1] == a[i]) 
        { 
            ++current_length; 
            if (longest_length < current_length) longest_length = current_length; 
        } 
        else 
        { 
            current_length = 1; 
        } 
    } 
 
    return longest_length; 
}

Запустим вышеприведенную демонстрационную программу с данным новым альтернативным определением функции:

#include <stdio.h> 
 
size_t max_subsequence_length( const int a[], size_t n ) 
{ 
    size_t longest_length = n != 0; 
 
    for (size_t i = 1, current_length = 1; i < n; i++) 
    { 
        if (a[i - 1] == a[i]) 
        { 
            ++current_length; 
        } 
        else 
        { 
            if (longest_length < current_length) longest_length = current_length; 
            current_length = 1; 
        } 
    } 
 
    return longest_length; 
} 
 
int main(void)  
{ 
    int a[] = { 2, 4, 4, 1, 3, 4, 4, 4, 4, 4, 6, 6, 6 }; 
    size_t n = sizeof( a ) / sizeof( *a ); 
     
    printf( "The longest length of duplicated elements is %zu.\n", max_subsequence_length( a, n ) ); 
}

Вывод программы на консоль будет точно таким же, как и в предыдущем запуске программы с первоначальным определением функции:

The longest length of duplicated elements is 5.

Казалось бы исходная задача решена, и можно поставить точку. Но давайте зададимся вопросом: а что делать, если тип массива, для которого требуется вызвать подобную функцию, будет изменен. Например, тип элементов массива будет не int, а long long int?

Будем писать точно такую же функцию, дублируя уже существующий код, и лишь изменив объявление функции? А что если вместо массивов арифметических типов потребуется выполнить точно такую же задачу для массивов указателей на строки? Строки бессмысленно сравнивать с помощью оператора сравнения ==, так как будут сравниваться не сами строки, а их адреса.

Выход из создавшейся ситуации - это использовать такой же подход, который реализован в стандартной C функции сортировки qsort. Эта функция вызывает функцию сравнения, в которой можно задать необходимое сравнение для любого типа элементов массива, обрабатываемого функцией qsort.

Вот как будет выглядеть определение этой обобщенной функции:

size_t max_subsequence_length1( const void *base, size_t nmemb, size_t size,  
                               int cmp( const void *, const void * ) ) 
{ 
    size_t longest_length = 0; 
     
    for ( size_t i = 0; i++ < nmemb; ) 
    { 
        size_t j = i - 1; 
         
        while ( i < nmemb && cmp( ( const char * )base + ( i - 1 ) * size, ( const char * )base + i * size ) == 0 ) ++i; 
         
        if ( longest_length < i - j ) longest_length = i - j; 
    } 
     
    return longest_length; 
}

В следующей демонстрационной программе показано, как использовать эту функцию для массивов разных типов. В качестве примера будут использоваться массив с элементами типа int, массив с элементами типа long long int, а также массив с элементами типа const char *:

#include <stdio.h> 
#include <string.h> 
 
size_t max_subsequence_length( const void *base, size_t nmemb, size_t size,  
                            int cmp( const void *, const void * ) ) 
{ 
    size_t longest_length = 0; 
     
    for ( size_t i = 0; i++ < nmemb; ) 
    { 
        size_t j = i - 1; 
         
        while ( i < nmemb && cmp( ( const char * )base + ( i - 1 ) * size, ( const char * )base + i * size ) == 0 ) ++i; 
         
        if ( longest_length < i - j ) longest_length = i - j; 
    } 
     
    return longest_length; 
} 
  
int cmp1( const void *p1, const void *p2 ) 
{ 
    int x = *( const int * )p1; 
    int y = *( const int * )p2; 
     
    return ( y < x ) - ( x < y ); 
} 
  
int cmp2( const void *p1, const void *p2 ) 
{ 
    long long int x = *( const long long int * )p1; 
    long long int y = *( const long long int * )p2; 
     
    return ( y < x ) - ( x < y ); 
} 
  
int cmp3( const void *p1, const void *p2 ) 
{ 
    const char *s1 = *( const char ** )p1; 
    const char *s2 = *( const char ** )p2; 
     
    return strcmp( s1, s2 ); 
} 
  
int main(void)  
{ 
    int a1[] = { 2, 4, 4, 1, 3, 4, 4, 4, 4, 4, 6, 6, 6 }; 
    size_t n1 = sizeof( a1 ) / sizeof( *a1 ); 
 
    printf( "The longest length of duplicated elements in a1 is %zu.\n", 
        max_subsequence_length( a1, n1, sizeof( *a1 ), cmp1 ) ); 
     
    long long int a2[] = { 2, 4, 4, 1, 3, 4, 4, 4, 4, 4, 6, 6, 6 }; 
    size_t n2 = sizeof( a2 ) / sizeof( *a2 ); 
 
    printf( "The longest length of duplicated elements in a2 is %zu.\n", 
        max_subsequence_length( a2, n2, sizeof( *a2 ), cmp2 ) ); 
     
    const char * a3[] =  
    {  
        "two", "four", "four", "one", "three", "four", "four", "four", "four", "four", "six", "six", "six"  
    }; 
    size_t n3 = sizeof( a3 ) / sizeof( *a3 ); 
 
    printf( "The longest length of duplicated elements in a3 is %zu.\n", 
        max_subsequence_length( a3, n3, sizeof( *a3 ), cmp3 ) ); 
}

Вывод программы на консоль:

The longest length of duplicated elements in a1 is 5. 
The longest length of duplicated elements in a2 is 5. 
The longest length of duplicated elements in a3 is 5.

В данной редакции нашей функции используется функция сравнения, определенная таким же образом, как это требуется для функции сравнения, используемой стандартной C функцией сортировки qsort.

Эти требования к функции сравнения в стандарте C24 (7.24.5.2 The qsort function) описываются следующим образом:

3 The contents of the array are sorted into ascending order according to a comparison function pointed to by compar, which is called with two arguments that point to the objects being compared. The function shall return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.

На самом деле это описание не совсем полное. Используя функцию qsort, можно сортировать массив не только в возрастающем порядке, но и в убывающем порядке. В последнем случае функция сравнения должна возвращать отрицательное целое число, ноль, или положительное целое число, если первый аргумент больше, равен, или меньше второго аргумента соответственно.

Ниже приведена демонстрационная программа сортировки массива в возрастающем и убывающем порядках:

#include <stdio.h> 
#include <stdlib.h> 
 
int cmp_ascending( const void *p1, const void *p2 ) 
{ 
    int x = *( const int * )p1; 
    int y = *( const int * )p2; 
 
    return ( y < x ) - ( x < y ); 
} 
 
int cmp_descending( const void *p1, const void *p2 ) 
{ 
    int x = *( const int * )p1; 
    int y = *( const int * )p2; 
 
    return ( x < y ) - ( y < x ); 
} 
 
int main( void ) 
{ 
    int a1[] = { 1, 0, 3, 2, 5, 4 }; 
    const size_t N1 = sizeof( a1 ) / sizeof( *a1 ); 
 
    qsort( a1, N1, sizeof( *a1 ), cmp_ascending ); 
 
    for (size_t i = 0; i < N1; i++) 
    { 
        printf( "%d ", a1[i] ); 
    } 
    putchar( '\n' ); 
 
    int a2[] = { 1, 0, 3, 2, 5, 4 }; 
    const size_t N2 = sizeof( a2 ) / sizeof( *a2 ); 
 
    qsort( a2, N2, sizeof( *a2 ), cmp_descending ); 
 
    for (size_t i = 0; i < N2; i++) 
    { 
        printf( "%d ", a2[i] ); 
    } 
    putchar( '\n' ); 
}

Результатом работы программы будет следующий вывод на консоль:

0 1 2 3 4 5  
5 4 3 2 1 0

Для нашей задачи нахождения длины максимальной подпоследовательности одинаковых элементов не требуется функция сравнения с таким детальным выводом результата. Достаточно просто использовать предикат, который будет возвращать либо логическое true, либо false в зависимости от того, удовлетворяют ли выбранные элементы заданному условию. Благодаря такому подходу понятие "одинаковых или равных элементов" массива может быть расширено - это смежные элементы массива, удовлетворяющие заданному условию.

Например, мы можем найти в массиве длину максимальной подпоследовательности не только действительно равных элементов, но также и длину максимальной подпоследовательности строго возрастающих по значению элементов, как показано в следующей демонстрационной программе:

#include <stdio.h> 
 
size_t max_subsequence_length( const void *base, size_t nmemb, size_t size,  
                            int predicate( const void *, const void * ) ) 
{ 
    size_t longest_length = 0; 
     
    for ( size_t i = 0; i++ < nmemb; ) 
    { 
        size_t j = i - 1; 
         
        while ( i < nmemb && predicate( ( const char * )base + ( i - 1 ) * size, ( const char * )base + i * size )  ) ++i; 
         
        if ( longest_length < i - j ) longest_length = i - j; 
    } 
     
    return longest_length; 
} 
  
int pred1( const void *p1, const void *p2 ) 
{ 
    int x = *( const int * )p1; 
    int y = *( const int * )p2; 
     
    return x == y; 
} 
  
int pred2( const void *p1, const void *p2 ) 
{ 
    int x = *( const int * )p1; 
    int y = *( const int * )p2; 
     
    return x < y; 
} 
  
int main(void)  
{ 
    int a1[] = { 2, 4, 4, 1, 3, 4, 4, 4, 4, 4, 6, 6, 6 }; 
    size_t n1 = sizeof( a1 ) / sizeof( *a1 ); 
 
    printf( "The longest length of duplicated elements in a1 is %zu.\n", 
        max_subsequence_length( a1, n1, sizeof( *a1 ), pred1 ) ); 
         
    int a2[] = { 1, 2, 3, 1, 2, 1, 2, 3, 4, 5, 1, 2, 3, 4 }; 
    size_t n2 = sizeof( a2 ) / sizeof( *a2 );  
     
    printf( "The longest length of duplicated elements in a2 is %zu.\n", 
        max_subsequence_length( a2, n2, sizeof( *a2 ), pred2 ) ); 
}

Круг применения этой функции достаточно ограничен. Чаще всего программистам требуется не просто найти длину максимальной подпоследовательности, но также желательно знать, с какого места в массиве начинается такая подпоследовательность, чтобы иметь к ней непосредственный доступ.

Чтобы добиться этого, следует изменить возвращаемое значение функции. Вместо скалярного значения типа size_t функция будет возвращать структуру, которая в качестве членов данных будет содержать адрес начала подпоследовательности и длину этой подпоследовательности в массиве. Будет естественно также переименовать функцию, так как функция предоставляет пользователям более объемлещую информацию, а не только одну длину максимальной подпоследовательности. Назовем ее max_subsequence.

Вот как теперь будет выглядеть функция:

struct range 
{ 
    void *position; 
    size_t length; 
}; 
 
struct range max_sequence( const void *base, size_t nmemb, size_t size, 
    int predicate( const void *, const void * ) ) 
{ 
    struct range max_seq = { .position = 0, .length = 0 }; 
 
    for ( size_t i = 0; i++ < nmemb; ) 
    { 
        size_t j = i - 1; 
 
        while ( i < nmemb && predicate( ( const char * )base + ( i - 1 ) * size, ( const char * )base + i * size ) ) ++i; 
 
        if ( max_seq.length < i - j ) 
        { 
            max_seq.position = ( void * )( ( const char * )base + j * size ); 
         
            max_seq.length = i - j; 
        } 
    } 
 
    return max_seq; 
}

В следующей демонстрационной программе на консоль будет выведена не только длина максимальных подпоследовательностей для нескольких массивов, но также и сами максимальные подпоследовательности этих массивов:

#include <stdio.h> 
#include <string.h> 
 
struct range 
{ 
    void *position; 
    size_t length; 
}; 
 
struct range max_sequence( const void *base, size_t nmemb, size_t size, 
    int predicate( const void *, const void * ) ) 
{ 
    struct range max_seq = { .position = 0, .length = 0 }; 
 
    for ( size_t i = 0; i++ < nmemb; ) 
    { 
        size_t j = i - 1; 
 
        while ( i < nmemb && predicate( ( const char * )base + ( i - 1 ) * size, ( const char * )base + i * size ) ) ++i; 
 
        if ( max_seq.length < i - j ) 
        { 
            max_seq.position = ( void * )( ( const char * )base + j * size ); 
         
            max_seq.length = i - j; 
        } 
    } 
 
    return max_seq; 
} 
 
int pred1( const void *p1, const void *p2 ) 
{ 
    int x = *( const int * )p1; 
    int y = *( const int * )p2; 
 
    return x == y; 
} 
 
int pred2( const void *p1, const void *p2 ) 
{ 
    int x = *( const int * )p1; 
    int y = *( const int * )p2; 
 
    return x < y; 
} 
 
int pred3( const void *p1, const void *p2 ) 
{ 
    const char *s1 = *( const char ** )p1; 
    const char *s2 = *( const char ** )p2; 
 
    return strcmp( s1, s2 ) == 0; 
} 
 
int main( void ) 
{ 
    int a1[] = { 2, 4, 4, 1, 3, 4, 4, 4, 4, 4, 6, 6, 6 }; 
    const size_t N1 = sizeof( a1 ) / sizeof( *a1 ); 
     
    printf( "a1: " ); 
    for ( size_t i = 0; i < N1; i++ ) 
    { 
        printf( "%d ", a1[i] ); 
    } 
    putchar( '\n' ); 
     
    struct range max_seq1 = max_sequence( a1, N1, sizeof( *a1 ), pred1 ); 
     
    printf( "%zu: ", max_seq1.length ); 
    for ( size_t i = 0; i < max_seq1.length; i++ ) 
    { 
        printf( "%d ", ( ( const int * )max_seq1.position )[i] ); 
    } 
    putchar( '\n' ); 
 
    putchar( '\n' ); 
 
    int a2[] = { 1, 0, 1, 2, 2, 3, 4, 5, 6, 1, 2 }; 
    const size_t N2 = sizeof( a2 ) / sizeof( *a2 ); 
     
    printf( "a2: " ); 
    for ( size_t i = 0; i < N2; i++ ) 
    { 
        printf( "%d ", a2[i] ); 
    } 
    putchar( '\n' ); 
     
    struct range max_seq2 = max_sequence( a2, N2, sizeof( *a2 ), pred2 ); 
     
    printf( "%zu: ", max_seq2.length ); 
    for ( size_t i = 0; i < max_seq2.length; i++ ) 
    { 
        printf( "%d ", ( ( const int * )max_seq2.position )[i] ); 
    } 
    putchar( '\n' ); 
 
    putchar( '\n' ); 
 
    const char * a3[] = 
    { 
        "two", "four", "four", "one", "three", "four", 
        "four", "four", "four", "four", "six", "six", "six" 
    }; 
    const size_t N3 = sizeof( a3 ) / sizeof( *a3 ); 
     
    printf( "a3: " ); 
    for ( size_t i = 0; i < N3; i++ ) 
    { 
        printf( "%s ", a3[i] ); 
    } 
    putchar( '\n' ); 
     
    struct range max_seq3 = max_sequence( a3, N3, sizeof( *a3 ), pred3 ); 
     
    printf( "%zu: ", max_seq3.length ); 
    for ( size_t i = 0; i < max_seq3.length; i++ ) 
    { 
        printf( "%s ", ( ( const char ** )max_seq3.position )[i] ); 
    } 
    putchar( '\n' ); 
}

Вывод программы на консоль:

a1: 2 4 4 1 3 4 4 4 4 4 6 6 6  
5: 4 4 4 4 4  
 
a2: 1 0 1 2 2 3 4 5 6 1 2  
5: 2 3 4 5 6  
 
a3: two four four one three four four four four four six six six 
5: four four four four four

Итак, начав с определения узкоспециализированной функции, которая в качестве аргументов принимает только целочисленные массивы с типом элементов int, и которая возвращает только длину максимальной подпоследовательности равных целых чисел, мы пришли к созданию достаточно универсальной и информативной функции, способной работать с массивами любого типа, возвращающей не только длину максимальной подпоследовательности, элементы которой удовлетворяют произвольному заданному пользователем условию, но также и позицию этой подпоследовательности внутри массива.

Но и это еще не все. Наша заключительная C функция поиска максимальной подпоследователности также имеет свои ограничения, и не всегда применима. Чтобы это продемонстрировать, перейдем от написания определения функции с языка программирования C на язык программирования C++, так как последний более гибкий и предоставляет больше возможностей в написании прикладного кода.

Для начала реализуем нашу C функцию в виде эквивалентного по функциональности C++ алгоритма. Вот как он будет выглядеть:

template <typename ForwardIterator, typename BinaryPredicate> 
std::pair<ForwardIterator, typename std::iterator_traits<ForwardIterator>::difference_type> 
max_sequence( ForwardIterator first, ForwardIterator last, BinaryPredicate binary_predicate ) 
{ 
    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type; 
 
    std::pair<ForwardIterator, difference_type> max_seq = { last, 0 }; 
 
    while (first != last) 
    { 
        auto initial = first; 
        difference_type current_length = 1; 
         
        for ( auto prev = first++; first != last && binary_predicate( *prev, *first ); ++first, ++prev ) 
        { 
            ++current_length; 
        } 
 
        if (max_seq.second < current_length) 
        { 
            max_seq = { initial, current_length }; 
        } 
    } 
 
    return max_seq; 
}

Чтобы убедиться, что алгоритм работает корректно и дает те же самые результаты, что и соответствующая C функция, в следующей демонстрационной программе будут использоваться те же самые массивы, что и в предыдущей демонстрационной программе, где задействована C функция:

#include <iostream> 
#include <utility> 
#include <iterator> 
 
#include <cstring> 
 
template <typename ForwardIterator, typename BinaryPredicate> 
std::pair<ForwardIterator, typename std::iterator_traits<ForwardIterator>::difference_type> 
max_sequence( ForwardIterator first, ForwardIterator last, BinaryPredicate binary_predicate ) 
{ 
    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type; 
 
    std::pair<ForwardIterator, difference_type> max_seq = { last, 0 }; 
 
    while (first != last) 
    { 
        auto initial = first; 
        difference_type current_length = 1; 
         
        for ( auto prev = first++; first != last && binary_predicate( *prev, *first ); ++first, ++prev ) 
        { 
            ++current_length; 
        } 
 
        if (max_seq.second < current_length) 
        { 
            max_seq = { initial, current_length }; 
        } 
    } 
 
    return max_seq; 
} 
 
int main() 
{ 
    int a1[] = { 2, 4, 4, 1, 3, 4, 4, 4, 4, 4, 6, 6, 6 }; 
 
    std::cout << "a1: "; 
    for ( const auto &item : a1 ) 
    { 
        std::cout << item << ' '; 
    } 
    std::cout << '\n'; 
     
    auto max_seq1 = max_sequence( std::begin( a1 ), std::end( a1 ), std::equal_to<>() ); 
     
    std::cout << max_seq1.second << ": "; 
    auto first1 = max_seq1.first; 
    for ( size_t i = 0; i < max_seq1.second; i++ ) 
    { 
        std::cout << *first1++ << ' '; 
    } 
    std::cout << '\n'; 
 
    std::cout << '\n'; 
 
    int a2[] = { 1, 0, 1, 2, 2, 3, 4, 5, 6, 1, 2 }; 
 
    std::cout << "a2: "; 
    for ( const auto &item : a2 ) 
    { 
        std::cout << item << ' '; 
    } 
    std::cout << '\n'; 
     
    auto max_seq2 = max_sequence( std::begin( a2 ), std::end( a2 ), std::less<>() ); 
     
    std::cout << max_seq2.second << ": "; 
    auto first2 = max_seq2.first; 
    for ( size_t i = 0; i < max_seq2.second; i++ ) 
    { 
        std::cout << *first2++ << ' '; 
    } 
    std::cout << '\n'; 
 
    std::cout << '\n'; 
 
    const char * a3[] = 
    { 
        "two", "four", "four", "one", "three", "four", 
        "four", "four", "four", "four", "six", "six", "six" 
    }; 
     
    std::cout << "a3: "; 
    for ( const auto &item : a3 ) 
    { 
        std::cout << item << ' '; 
    } 
    std::cout << '\n'; 
     
    auto max_seq3 = max_sequence( std::begin( a3 ), std::end( a3 ),  
        []( const auto &left, const auto &right ) 
        { 
            return std::strcmp( left, right ) == 0; 
        } ); 
     
    std::cout << max_seq3.second << ": "; 
    auto first3 = max_seq3.first; 
     
    for ( size_t i = 0; i < max_seq3.second; i++ ) 
    { 
        std::cout << *first3++ << ' '; 
    } 
    std::cout << '\n'; 
}

Вывод программы на консоль:

a1: 2 4 4 1 3 4 4 4 4 4 6 6 6  
5: 4 4 4 4 4  
 
a2: 1 0 1 2 2 3 4 5 6 1 2  
5: 2 3 4 5 6  
 
a3: two four four one three four four four four four six six six  
5: four four four four four

Как видно, выводы обеих демонстрационных программ, демонстрационной программы C функции и демонстрационной программы C++ алгоритма, на консоль идентичны.

Рассмотрим еще один пример работы алгоритма. Постараемся найти максимальную подпоследовательность чередующихся четных и нечетных чисел в массиве. Ниже представлена соответствующая программа:

#include <iostream> 
#include <iterator> 
 
template <typename ForwardIterator, typename BinaryPredicate> 
std::pair<ForwardIterator, typename std::iterator_traits<ForwardIterator>::difference_type> 
max_sequence( ForwardIterator first, ForwardIterator last, BinaryPredicate binary_predicate ) 
{ 
    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type; 
 
    std::pair<ForwardIterator, difference_type> max_seq = { last, 0 }; 
 
    while (first != last) 
    { 
        auto initial = first; 
        difference_type current_length = 1; 
         
        for ( auto prev = first++; first != last && binary_predicate( *prev, *first ); ++first, ++prev ) 
        { 
            ++current_length; 
        } 
 
        if (max_seq.second < current_length) 
        { 
            max_seq = { initial, current_length }; 
        } 
    } 
 
    return max_seq; 
} 
 
int main() 
{ 
    int a[] = { 1, 0, 1, 2, 2, 3, 4, 5, 6, 1, 2, 0, 1, 2, 3, 4, 5 }; 
     
    std::cout << "a: "; 
    for ( const auto &item : a ) 
    { 
        std::cout << item << ' '; 
    } 
    std::cout << '\n'; 
     
    auto check_even_odd =  
        [even_or_odd = true]( const auto &prev, const auto &next ) mutable 
        { 
            enum order : bool { Even = true, Odd = false }; 
 
            bool result; 
 
            switch ( even_or_odd ) 
            { 
            case Odd: 
                result = prev % 2 == 1 && next % 2 == 0; 
                even_or_odd = true; 
                break; 
 
            case Even: 
                result = prev % 2 == 0 && next % 2 == 1; 
                even_or_odd = !result; 
            } 
 
            return result; 
        }; 
 
    auto max_seq = max_sequence( std::begin( a ), std::end( a ), check_even_odd ); 
     
    std::cout << '\n'; 
             
    for ( auto first = std::cbegin( a ), last = std::cend( a ); first != last; ) 
    { 
        for ( auto first_range_last = max_seq.first; 
            first != first_range_last; ++first ) 
        { 
            std::cout << *first << ' '; 
        } 
        std::cout << '\n'; 
 
        std::cout << "The length of the maximum sequence of even-odd elements is " 
            << max_seq.second << ": "; 
 
        for ( size_t i = 0; i < max_seq.second; i++ ) 
        { 
            std::cout << *first++ << ' '; 
        } 
        std::cout << '\n'; 
 
        for ( ; first != last; ++first ) 
        { 
            std::cout << *first << ' '; 
        } 
        std::cout << '\n'; 
    } 
}

Вывод программы на консоль:

a: 1 0 1 2 2 3 4 5 6 1 2 0 1 2 3 4 5  
 
1 0 1 2  
The length of the maximum sequence of even-odd elements is 7: 2 3 4 5 6 1 2  
0 1 2 3 4 5

Результат работы алгоритма для используемого массива совершенно верный. Казалось бы алгоритм работает корректно для данного заданного условия. Однако в нем имеется один изъян. Алгоритм с данным условием будет работать корректно, если массив или иной контейнер содержит более одного элемента. В случае, когда массив или иной контейнер содержит только один элемент, то он не может быть проверен, является ли он четным или нечетным, так как передаваемый в алгоритм предикат работает только с двумя элементами массива или контейнера.

Что делать в таком случае?

Например, мы могли бы проверять перед вызовом алгоритма, содержит ли массив или иной контейнер только один элемент, и является ли он четным, как это требуется заданным условием. Но это было бы явным дефектом самого алгоритма.

Правильным решением будет перегрузить алгоритм таким образом, что его дополнительная новая редакция будет содержать помимо бинарного предиката еще и унарный предикат, который предназначен для поиска и проверки первого элемента последовательности, удовлетворяющего заданному условию.

Вот как будет выглядеть дополнительный алгоритм:

template <typename ForwardIterator, typename UnaryPredicate, typename BinaryPredicate> 
std::pair<ForwardIterator, typename std::iterator_traits<ForwardIterator>::difference_type> 
max_sequence( ForwardIterator first,  
    ForwardIterator last,  
    UnaryPredicate unary_predicate, 
    BinaryPredicate binary_predicate ) 
{ 
    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type; 
 
    std::pair<ForwardIterator, difference_type> max_seq = { last, 0 }; 
 
    while ( first != last ) 
    { 
        first = std::find_if( first, last, unary_predicate ); 
 
        if ( first != last ) 
        { 
            auto initial = first; 
            difference_type current_length = 1; 
 
            for ( auto prev = first++; first != last && binary_predicate( *prev, *first ); ++first, ++prev ) 
            { 
                ++current_length; 
            } 
 
            if ( max_seq.second < current_length ) 
            { 
                max_seq = { initial, current_length }; 
            } 
        } 
    } 
 
    return max_seq; 
}

Ниже приведена демонстрационная программа, в которой наш новый алгоритм правильно определяет максимальную последовательность чередующихся четных и нечетных чисел в массивах, содержащих всего лишь один элемент. То есть, например, когда такой массив содержит лишь одно нечетное число, то, естественно, длина максимальной подпоследовательности четных и нечетных чисел будет равна 0:

#include <iostream> 
#include <iterator> 
#include <algorithm> 
  
template <typename ForwardIterator, typename UnaryPredicate, typename BinaryPredicate> 
std::pair<ForwardIterator, typename std::iterator_traits<ForwardIterator>::difference_type> 
max_sequence( ForwardIterator first,  
    ForwardIterator last,  
    UnaryPredicate unary_predicate, 
    BinaryPredicate binary_predicate ) 
{ 
  
    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type; 
  
    std::pair<ForwardIterator, difference_type> max_seq = { last, 0 }; 
  
    while ( first != last ) 
    { 
        first = std::find_if( first, last, unary_predicate ); 
  
        if ( first != last ) 
        { 
            auto initial = first; 
            difference_type current_length = 1; 
  
            for ( auto prev = first++; first != last && binary_predicate( *prev, *first ); ++first, ++prev ) 
            { 
                ++current_length; 
            } 
  
            if ( max_seq.second < current_length ) 
            { 
                max_seq = { initial, current_length }; 
            } 
        } 
    } 
  
    return max_seq; 
} 
  
int main() 
{ 
    auto even = true; 
  
    auto check_even_odd =  
    [&even_or_odd = even]( const auto &prev, const auto &next ) 
    { 
        enum order : bool { Even = true, Odd = false }; 
  
        bool result; 
  
        switch ( even_or_odd ) 
        { 
        case Odd: 
            result = prev % 2 == 1 && next % 2 == 0; 
            even_or_odd = true; 
            break; 
  
        case Even: 
            result = prev % 2 == 0 && next % 2 == 1; 
            even_or_odd = !result; 
        } 
  
        return result; 
    }; 
  
    int a1[] = { 1 }; 
  
    std::cout << "a1: "; 
    for ( const auto &item : a1 ) 
    { 
        std::cout << item << ' '; 
    } 
    std::cout << '\n'; 
  
    auto max_seq1 = max_sequence( std::begin( a1 ), std::end( a1 ),  
        []( const auto &current ) { return current % 2 == 0; }, 
        check_even_odd ); 
  
    std::cout << max_seq1.second << ": "; 
  
    auto first1 = max_seq1.first; 
    for ( size_t i = 0; i < max_seq1.second; i++ ) 
    { 
        std::cout << *first1++ << ' '; 
    } 
    std::cout << '\n'; 
     
    std::cout << '\n'; 
  
    int a2[] = { 2 }; 
  
    std::cout << "a2: "; 
    for ( const auto &item : a2 ) 
    { 
        std::cout << item << ' '; 
    } 
    std::cout << '\n'; 
  
    even = true; 
    auto max_seq2 = max_sequence( std::begin( a2 ), std::end( a2 ),  
        []( const auto &current ) { return current % 2 == 0; }, 
        check_even_odd ); 
  
    std::cout << max_seq2.second << ": "; 
  
    auto first2 = max_seq2.first; 
    for ( size_t i = 0; i < max_seq2.second; i++ ) 
    { 
        std::cout << *first2++ << ' '; 
    } 
    std::cout << '\n'; 
     
    std::cout << '\n'; 
  
    int a3[] = { 1, 0, 1, 2, 2, 3, 4, 5, 6, 1, 2, 0, 1, 2, 3, 4, 5 }; 
  
    std::cout << "a3: "; 
    for ( const auto &item : a3 ) 
    { 
        std::cout << item << ' '; 
    } 
    std::cout << '\n'; 
  
    even = true; 
    auto max_seq3 = max_sequence( std::begin( a3 ), std::end( a3 ),  
        []( const auto &current ) { return current % 2 == 0; }, 
        check_even_odd ); 
  
    std::cout << max_seq3.second << ": "; 
  
    auto first3 = max_seq3.first; 
    for ( size_t i = 0; i < max_seq3.second; i++ ) 
    { 
        std::cout << *first3++ << ' '; 
    } 
    std::cout << '\n'; 
}

Вывод программы на консоль:

a1: 1  
0:  
 
a2: 2  
1: 2  
 
a3: 1 0 1 2 2 3 4 5 6 1 2 0 1 2 3 4 5  
7: 2 3 4 5 6 1 2

Проверка всей последовательности на чередование чётных и нечётных чисел​

А как проверить, представляют ли все элементы массива или иного контейнера последовательность чередующихся четных и нечетных чисел?

Для этого достаточно использовать стандартный алгоритм std::all_of, как это показано в ниже приведенной демонстрационной программе:

#include <iostream> 
#include <iterator> 
#include <algorithm> 
  
int main() 
{ 
    bool after_even_odd = false; 
     
    auto check_even_odd = [&after_even_odd]( const auto &item ) 
    { 
        return after_even_odd = !after_even_odd, 
               after_even_odd && item % 2 == 0 || !after_even_odd && item % 2 == 1; 
    }; 
         
    int a1[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
 
    auto result = std::all_of( std::begin( a1 ), std::end( a1 ), check_even_odd ); 
     
    std::cout << std::boolalpha; 
     
    std::cout << "The array a1 contains a sequence of alternating even-odd numbers is " 
        << result << '\n'; 
 
 
    int a2[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; 
     
    after_even_odd = true; 
 
    result = std::all_of( std::begin( a2 ), std::end( a2 ), check_even_odd ); 
     
    std::cout << "The array a2 contains a sequence of alternating odd-even numbers is " 
        << result << '\n'; 
}

Вывод программы на консоль:

The array a1 contains a sequence of alternating even-odd numbers is true 
The array a2 contains a sequence of alternating odd-even numbers is true

Но, давайте вернемся к исходной задаче: нахождение максимальной подпоследовательности равных элементов. Можем ли мы использовать наш алгоритм с двумя предикатами для решения этой задачи? Ведь первым элементом подпоследовательности может быть любой элемент массива или иного контейнера. На самом деле сделать это не сложно. Достаточно, например, при вызове алгоритма указать лямбда-выражение вида:

[]( const auto & ) { return true; }

Но код вызова алгоритма с таким лямбда-выражением будет менее ясным, так как читающему код нужно будет вникать, что делает лямбда-выражение. Код будет более ясным, если в вызове алгоритма будет присутствовать предикат, имя которого недвусмысленно говорит, какова его функция. Итак, определим следующие два предиката:

template <typename T = void> 
struct true_predicate 
{ 
    constexpr bool operator ()( const T & ) const 
    { 
        return true; 
    } 
}; 
 
template <> 
struct true_predicate<void> 
{ 
    template <typename T> 
    constexpr bool operator ()( T && ) const 
    { 
        return true; 
    } 
}; 
 
template <typename T = void> 
struct false_predicate 
{ 
    constexpr bool operator ()( const T & ) const 
    { 
        return false; 
    } 
}; 
 
template <>  
struct false_predicate<void> 
{ 
    template<class T> 
    constexpr bool operator()( T && ) const 
    { 
        return false; 
    } 
};

Используя алгоритм с двумя предикатами и первый из вышеприведенных двух предикатов, найдем в массиве максимальную подпоследовательность равных элементов, как это ранее делалось с помощью алгоритма, имеющего один бинарный предикат:

#include <iostream> 
#include <utility> 
#include <iterator> 
#include <algorithm> 
  
template <typename ForwardIterator, typename UnaryPredicate, typename BinaryPredicate> 
std::pair<ForwardIterator, typename std::iterator_traits<ForwardIterator>::difference_type> 
max_sequence( ForwardIterator first,  
    ForwardIterator last,  
    UnaryPredicate unary_predicate, 
    BinaryPredicate binary_predicate ) 
{ 
  
    using difference_type = typename std::iterator_traits<ForwardIterator>::difference_type; 
  
    std::pair<ForwardIterator, difference_type> max_seq = { last, 0 }; 
  
    while ( first != last ) 
    { 
        first = std::find_if( first, last, unary_predicate ); 
  
        if ( first != last ) 
        { 
            auto initial = first; 
            difference_type current_length = 1; 
  
            for ( auto prev = first++; first != last && binary_predicate( *prev, *first ); ++first, ++prev ) 
            { 
                ++current_length; 
            } 
  
            if ( max_seq.second < current_length ) 
            { 
                max_seq = { initial, current_length }; 
            } 
        } 
    } 
  
    return max_seq; 
} 
  
template <typename T = void> 
struct true_predicate 
{ 
    constexpr bool operator ()( const T & ) const 
    { 
        return true; 
    } 
}; 
 
template <> 
struct true_predicate<void> 
{ 
    template <typename T> 
    constexpr bool operator ()( T && ) const 
    { 
        return true; 
    } 
}; 
 
template <typename T = void> 
struct false_predicate 
{ 
    constexpr bool operator ()( const T & ) const 
    { 
        return false; 
    } 
}; 
 
template <>  
struct false_predicate<void> 
{ 
    template<class T> 
    constexpr bool operator()( T && ) const 
    { 
        return false; 
    } 
}; 
 
 
int main() 
{ 
    int a[] = { 2, 4, 4, 1, 3, 4, 4, 4, 4, 4, 6, 6, 6 }; 
     
    std::cout << "a: "; 
    for ( const auto &item : a ) 
    { 
        std::cout << item << ' '; 
    } 
    std::cout << '\n'; 
  
    auto max_seq = max_sequence( std::begin( a ), std::end( a ), 
        true_predicate<>(), 
        std::equal_to<>() ); 
 
    std::cout << max_seq.second << ": "; 
  
    auto first = max_seq.first; 
    for ( size_t i = 0; i < max_seq.second; i++ ) 
    { 
        std::cout << *first++ << ' '; 
    } 
    std::cout << '\n'; 
}

Вывод программы на консоль:

a: 2 4 4 1 3 4 4 4 4 4 6 6 6  
5: 4 4 4 4 4

В этой программе предикат false_predicate не используется, но приведен для полноты описания определенных выше двух предикатов.

Здесь мы поставим точку в нашем изложении. Где-то же надо ставить точку? Хотя я уверен, что найдется немало программистов, которые могут предложить свои идеи, исправления, дополнения и замечания к представленному материалу. Программирование - это творческий процесс. Как говорится, потянешь за ниточку, вытянишь целый клубок. Вот почему стандарты языков программирования находятся в постоянном развитии.