Число локальных максимумов

1. Идея

Нужно посчитать, сколько элементов массива являются локальными вершинами.

По определению, точка с индексом i является локальной вершиной, если:

• она не первая и не последняя, то есть 1 <= i <= n - 2;
• её значение строго больше обоих соседей:
  • a[i] > a[i - 1]
  • a[i] > a[i + 1]

Значит, достаточно пройти по всем внутренним элементам массива и проверить это условие.

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

1. Первый и последний элементы никогда не могут быть локальными вершинами, потому что у них нет двух соседей.

2. Для каждого элемента достаточно посмотреть только на его левого и правого соседа.

3. Если n < 3, локальных вершин быть не может, потому что в массиве нет ни одного внутреннего элемента.

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

3. Алгоритм

1. Считать n.
2. Считать массив a из n чисел.
3. Завести переменную ans = 0.
4. Для каждого индекса i от 1 до n - 2:
   • если a[i] > a[i - 1] и a[i] > a[i + 1], увеличить ans на 1.
5. Вывести ans.

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

Мы перебираем все и только те позиции, которые вообще могут быть локальными вершинами: от 1 до n - 2.

Для каждой такой позиции проверяется точное условие из задачи: значение в текущей точке должно быть строго больше левого и правого соседей.

• Если условие выполнено, эта точка действительно является локальной вершиной, и мы увеличиваем ответ.
• Если условие не выполнено, эта точка не является локальной вершиной, и в ответ она не входит.

Так как каждая подходящая позиция проверяется ровно один раз, а неподходящие позиции не учитываются, итоговое значение ans равно количеству локальных вершин в профиле.

5. Сложность

• Время: O(n), потому что массив просматривается один раз.
• Память: O(n) на хранение массива.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

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

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int ans = 0;
    for (int i = 1; i + 1 < n; i++) {
        if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
            ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

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

ans = 0
for i in range(1, n - 1):
    if a[i] > a[i - 1] and a[i] > a[i + 1]:
        ans += 1

print(ans)