1. Идея

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

Самый прямой путь: идти по массиву слева направо и поддерживать две величины:

• mx — текущий максимальный балл среди уже просмотренных;
• cnt — сколько раз этот максимум встретился.

Когда читаем очередное число:

• если оно больше mx, найден новый максимум, значит:
  • обновляем mx,
  • сбрасываем cnt в 1;
• если оно равно mx, просто увеличиваем cnt;
• если оно меньше mx, ничего делать не нужно.

В конце cnt и будет ответом.

2. Наблюдения

1. Не нужно хранить никакую сложную информацию о массиве. Для ответа достаточно знать только текущий максимум и число его вхождений.

2. Если встретилось число больше текущего максимума, все прежние подсчёты уже не важны: старый максимум перестаёт быть максимальным, поэтому счётчик нужно начать заново.

3. Если очередное число равно текущему максимуму, это ещё одно вхождение максимума, значит cnt увеличивается на 1.

4. Ограничение n <= 2 * 10^5 легко позволяет пройти по массиву один раз.

3. Алгоритм

1. Считать n.
2. Считать массив из n чисел.
3. Инициализировать:
   • mx = a[0]
   • cnt = 1
4. Для каждого элемента массива, начиная со второго:
   • если a[i] > mx:
     • mx = a[i]
     • cnt = 1
   • иначе если a[i] == mx:
     • cnt += 1
5. Вывести cnt.

4. Почему это работает

Докажем, что после обработки первых i элементов:

• mx равен максимуму среди этих i элементов;
• cnt равен числу вхождений этого максимума среди этих i элементов.

База

После чтения первого элемента:

• максимум среди одного элемента — это сам первый элемент;
• число его вхождений равно 1.

Значит, изначально всё верно.

Переход

Пусть после обработки некоторой части массива утверждение верно. Рассмотрим следующий элемент x.

Случай 1: x > mx

Тогда новый максимум всей просмотренной части — это x. Он встретился пока только один раз, значит нужно сделать:

• mx = x
• cnt = 1

Это правильно.

Случай 2: x == mx

Максимум не изменился, но встретился ещё один такой элемент. Значит число его вхождений увеличивается на 1.

Это тоже правильно.

Случай 3: x < mx

Максимум не изменился и число его вхождений тоже не изменилось.

И это правильно.

Во всех случаях после обработки очередного элемента инвариант сохраняется. Значит, после обработки всего массива cnt действительно равно количеству вхождений максимального элемента.

5. Сложность

• Время: O(n), потому что каждый элемент рассматривается один раз.
• Память:
  • для приведённого решения на C++ — O(1), так как числа можно обрабатывать по мере чтения;
  • для приведённого решения на Python — O(n), так как массив считывается целиком в список.

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long x;
    cin >> x;
    long long mx = x;
    int cnt = 1;

    for (int i = 1; i < n; i++) {
        cin >> x;
        if (x > mx) {
            mx = x;
            cnt = 1;
        } else if (x == mx) {
            cnt++;
        }
    }

    cout << cnt << "\n";
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

mx = a[0]
cnt = 1

for i in range(1, n):
    if a[i] > mx:
        mx = a[i]
        cnt = 1
    elif a[i] == mx:
        cnt += 1

print(cnt)