Разбор задачи «Тропа разведчика»

Краткая суть задачи

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

Иначе говоря, требуется найти максимальную длину такого отрезка a[l..r], что

• a[l] < a[l + 1] < a[l + 2] < ... < a[r]
• все элементы идут подряд, без пропусков.

Главное наблюдение

Нас интересуют именно непрерывные возрастающие участки.

Это очень важно. Если бы задача была про просто возрастающую подпоследовательность, можно было бы пропускать элементы. Но здесь так делать нельзя.

Например, в массиве

1 3 5 4 7

• участок 1 3 5 подходит, его длина 3
• участок 4 7 тоже подходит, его длина 2
• взять 1 3 5 7 нельзя, потому что между 5 и 7 стоит 4, а пропускать элементы запрещено

Значит, задача сводится к очень простому процессу:

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

Как будем хранить ответ

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

• cur — длина текущего непрерывного строго возрастающего участка,
• best — максимальная длина среди всех уже рассмотренных участков.

Переход

Для каждого i от 1 до n - 1:

• если a[i] > a[i - 1], то текущий участок продолжается, значит cur += 1
• иначе возрастающий участок оборвался, и теперь текущий участок состоит только из одного элемента, то есть cur = 1

После этого обновляем:

• best = max(best, cur)

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

Рассмотрим позицию i.

Есть только два варианта:

1. a[i] > a[i - 1]

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

Значит, длина текущего участка увеличивается на 1.

2. a[i] <= a[i - 1]

Тогда участок, заканчивавшийся в i - 1, продолжить уже нельзя.

Любой возрастающий непрерывный участок, заканчивающийся в i, может состоять только из самого элемента a[i]. Поэтому cur = 1.

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

Разбор примера

Пусть дан массив:

1 3 5 4 7

Изначально:

• cur = 1
• best = 1

Дальше идём по массиву:

i = 1

3 > 1, значит участок продолжается:

• cur = 2
• best = 2

i = 2

5 > 3, участок продолжается:

• cur = 3
• best = 3

i = 3

4 > 5 — неверно, участок оборвался:

• cur = 1
• best = 3

i = 4

7 > 4, начинается новый возрастающий участок:

• cur = 2
• best = 3

Ответ: 3.

Отдельно про крайние случаи

Пустой массив

Если n = 0, то элементов нет, значит ответ равен 0.

Один элемент

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

Все элементы равны

Например: 2 2 2 2

Так как требуется строгое возрастание, равные соседние элементы не подходят. Значит, ответ будет 1.

Массив полностью возрастает

Например: 1 2 3 4 5

Тогда ответ равен n.

Массив полностью убывает

Например: 5 4 3 2 1

Тогда каждый элемент образует только участок длины 1, значит ответ равен 1.

Сложность

Мы один раз проходим по массиву.

• Время: O(n)
• Память: O(1)

Это оптимальное решение, потому что все элементы всё равно нужно хотя бы прочитать.

Эталонное решение на C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

    if (n == 0) {
        cout << 0 << '\n';
        return 0;
    }

    int cur = 1;
    int best = 1;

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

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

Эталонное решение на Python

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

if n == 0:
    print(0)
else:
    cur = 1
    best = 1

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

        if cur > best:
            best = cur

    print(best)

Частые ошибки

1. Путают подмассив и подпоследовательность

Это самая частая ошибка.

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

2. Используют нестрогое сравнение

Нужно писать именно:

• a[i] > a[i - 1]

Если написать >=, то равные элементы ошибочно будут считаться продолжением возрастающего участка.

3. Забывают случай n = 0

Если массив пустой, нельзя инициализировать ответ как 1 без проверки.

4. Неправильно обновляют максимум

После изменения cur нужно не забыть обновить best.