Самая длинная серия погоды — разбор

1. Идея

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

Будем идти слева направо и поддерживать:

• cur — длину текущей серии одинаковых чисел;
• ans — максимальную длину серии, которую уже встретили.

Если очередной элемент равен предыдущему, текущая серия продолжается, значит cur увеличивается на 1.

Если не равен, значит началась новая серия длины 1, поэтому cur = 1.

После этого обновляем ответ: ans = max(ans, cur).

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

1. Серия — это именно непрерывный отрезок. То есть одинаковые значения в разных местах массива нельзя объединять.

2. Для каждой позиции i важно только одно: равен ли a[i] предыдущему элементу a[i - 1].

3. Не нужно хранить никакие сложные структуры данных. Достаточно одного прохода по массиву.

4. Если n = 1, ответ сразу равен 1, потому что единственный день уже образует серию длины 1.

3. Алгоритм

1. Считываем n.
2. Считываем массив a из n чисел.
3. Инициализируем:
   • ans = 1
   • cur = 1
4. Для всех i от 1 до n - 1:
   • если a[i] == a[i - 1], то cur += 1;
   • иначе cur = 1;
   • обновляем ans, если cur стал больше.
5. Выводим ans.

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

Докажем, что алгоритм действительно находит длину самой длинной серии.

Рассмотрим, что означает переменная cur после обработки позиции i:

• если a[i] == a[i - 1], то серия, заканчивающаяся в i - 1, продолжается, поэтому ее длина увеличивается на 1;
• если a[i] != a[i - 1], то старая серия закончилась, и в позиции i начинается новая серия длины 1.

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

Тогда ans, как максимум всех значений cur, будет равна длине самой длинной серии во всем массиве.

Следовательно, алгоритм корректен.

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 = 1;
    int cur = 1;

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

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

7. Код на Python 3

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

ans = 1
cur = 1

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

print(ans)