Как мы можем найти второй максимум от массива эффективно?

Шаг 1. Определитесь с первыми двумя числами.
Шаг 2. Просмотрите оставшиеся числа.
Шаг 3. Сохраняйте последний максимум и второй максимум.
Шаг 4. При обновлении второго максимума помните, что вы не уравниваете максимальное значение и второе максимальное значение.

Протестировано для сортировки ввода (по возрастанию и убыванию), случайного ввода, ввода с дубликатами, работает нормально.

#include <iostream>
#define MAX 50
int GetSecondMaximum(int* data, unsigned int size)
{
    int max, secmax;
    // Decide on first two numbers
    if (data[0] > data[1])
    {
        max = data[0];
        secmax = data[1];
    }
    else
    {
        secmax = data[0];
        max = data[1];
    }
    // Loop through remaining numbers
    for (unsigned int i = 2; i < size; ++i)
    {
        if (data[i] > max)
        {
            secmax = max;
            max = data[i];
        }
        else if (data[i] > secmax && data[i] != max/*removes duplicate problem*/)
            secmax = data[i];
    }
    return secmax;
}
int main()
{
    int data[MAX];
    // Fill with random integers
    for (unsigned int i = 0; i < MAX; ++i)
    {
        data[i] = rand() % MAX;
        std::cout << "[" << data[i] << "] "; // Display input
    }
    std::cout << std::endl << std::endl;
    // Find second maximum
    int nSecondMax = GetSecondMaximum(data, MAX);
    // Display output
    std::cout << "Second Maximum = " << nSecondMax << std::endl;
    // Wait for user input
    std::cin.get();
    return 0;
}

Quickselect - это то, что нужно. Псевдокод доступен по этой ссылке, поэтому я просто объясню общий алгоритм:

QuickSelect for kth largest number:
    Select a pivot element
    Split array around pivot
    If (k < new pivot index)
       perform quickselect on left hand sub array
     else if (k > new pivot index)
       perform quickselect on right hand sub array (make sure to offset k by size of lefthand array + 1)
     else
       return pivot

Он совершенно очевидно основан на старом добром алгоритме квиксорта.

Следуя этому алгоритму, каждый раз выбирая нулевой элемент в качестве стержня:

select 4th largest number:
1) array = {1, 3, 2, 7, 11, 0, -4}
partition with 1 as pivot
{0, -4, _1_, 3, 2, 7, 11}
4 > 2 (new pivot index) so...

2) Select 1st (4 - 3) largest number from right sub array
array = {3, 2, 7, 11}
partition with 3 as pivot
{2, _3_, 7, 11}
1 < 2 (new pivot index) so...

3) select 1st largest number from left sub array
array = {2}

4) Done, 4th largest number is 2

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

Вот, пожалуйста:

std::pair<int, int> GetTwoBiggestNumbers(const std::vector<int>& array)
{
    std::pair<int, int> biggest;
    biggest.first = std::max(array[0], array[1]);  // Biggest of the first two.
    biggest.second = std::min(array[0], array[1]); // Smallest of the first two.

    // Continue with the third.
    for(std::vector<int>::const_iterator it = array.begin() + 2;
        it != array.end();
        ++it)
    {
        if(*it > biggest.first)
        {
            biggest.second = biggest.first;
            biggest.first = *it;
        }
        else if(*it > biggest.second)
        {
            biggest.second = *it;
        }
    }

    return biggest;
}

Вам нужен второй тест:

 for(int i=0;i<5;i++){  
   if(arr[i]>max){  
     second_max=max;  
     max=arr[i];            
   }
   else if (arr[i] > second_max && arr[i] != max){
     second_max = arr[i];
   }
 }

Самым простым решением было бы использование std::nth_element.

Другой способ решить эту проблему - использовать сравнения между элементами. Например,

a[10] = {1,2,3,4,5,6,7,8,9,10}

Сравните 1,2 и скажите max = 2 и second max = 1

Теперь сравните 3 и 4 и сравните наибольшее из них с max.

if element > max
     second max = max
     element = max
else if element > second max
     second max = element

Преимущество этого метода в том, что вы исключаете два числа всего за два сравнения.

Дайте мне знать, если у вас возникнут проблемы с пониманием этого.

Ваш исходный код в порядке, вам просто нужно инициализировать переменные max и second_max. Используйте первые два элемента в массиве.