§ 13. Максимальный и минимальный элементы массива

13.1. Поиск максимального (минимального) элемента в массиве

Очень часто для решения задачи требуется находить не заданный элемент массива, а максимальный (наибольший) или минимальный (наименьший) элемент.

Рассмотрим задачу нахождения максимального элемента. Если в массиве один-единственный элемент, то он и есть максимальный. Если элементов больше одного, то максимальным в массиве из i элементов является максимум из a[i] и максимального среди первых i - 1 элементов. Находить максимум будем последовательно, сравнивая текущий элемент с максимумом, найденным на предыдущем шаге. Если текущий элемент больше, то значение максимума, найденное на предыдущем шаге, нужно обновить (пример 13.1).

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

Будем использовать переменную n_max для хранения индекса максимального элемента. Значение переменной n_max будет изменятся тогда, когда изменяется значение максимального элемента (пример 13.2).

Если в массиве несколько элементов имеют максимальное значение, то значением переменной n_max будет индекс первого из них. Если использовать условие a[i] >= max, то переменная n_max будет хранить индекс последнего из максимальных элементов.

Если известен индекс i элемента массива, то значение этого элемента можно получить, обратившись к элементу по индексу: a[i]. Поэтому при поиске максимального элемента достаточно хранить только его индекс n_max. Значение максимального элемента — a[n_max] (пример 13.3).

Поиск минимального элемента осуществляется аналогично. В программе достаточно заменить знак > в условии оператора ветвления на знак < (пример 13.4). Имя переменной для хранения номера минимального элемента — n_min.

Пример 13.1.

V. Программа:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  for (int i = 0; i < n; i++)

    cin >> a[i];

  //поиск максимального элемента

  int Max = a[0];

  for (int i = 1; i < n; i++)

    if (a[i] > Max)

      Max = a[i];

  cout << "max = " << Max;

  cout << endl;

  return 0;

}

VI. Тестирование.

Пример 13.2.

V. Программа:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  for (int i = 0; i < n; i++)

    cin >> a[i];

  //поиск максимального элемента

  int Max = a[0], n_max = 0;

  for (int i = 1; i < n; i++)

    if (a[i] > Max){

      Max = a[i];

      n_max = i;

    }

  cout << "max = " << Max;

  cout << " ego mesto " << n_max;

  cout << endl;

  return 0;

}

VI. Тестирование.

Пример 13.3. Фрагмент программы:

int n_max = 0;

for (int i = 1; i < n; i++)

  if (a[i] > a[n_max])

    n_max = i;

cout << "max = " << a[n_max];

cout << " ego mesto " << n_max;

Пример 13.4. Фрагмент программы:

int n_min = 0;

for (int i = 1; i < n; i++)

  if (a[i] < a[n_min])

    n_min = i;