Перебор списка с условием

Считать элементы по условию вы умеете с занятия про накопление: завёл счётчик, прошёл, посчитал. Список ничего к этому не добавляет.

Зато он добавляет три вещи, которых у потока не было:

Пройти данные дважды. Задача «сколько элементов больше среднего» в потоке нерешаема: пока не прочитано всё, среднее неизвестно, а прочитанное уже забыто. Со списком — два прохода, и всё.

a = list(map(int, input().split()))
average = sum(a) / len(a)          # первый проход — внутри sum

count = 0
for x in a:                        # второй проход
    if x > average:
        count += 1

Посмотреть вперёд. «Элемент больше обоих соседей» требует знать следующий, а он в потоке ещё не пришёл.

Обратиться по номеру. «Сумма $k$ подряд идущих», «что стоит между позициями» — всё это про номера, которых у потока нет вовсе.

Отсюда и задачи занятия: не «посчитать по условию» вообще, а именно те условия, которые без списка не проверить.

Две почти одинаковые задачи с разными решениями.

Первый подходящий. Нашли — и выходим: дальше искать нечего.

answer = 0
for i in range(len(a)):
    if a[i] > x:
        answer = i + 1
        break            # выход сразу
print(answer)

Последний подходящий. Прерывать нельзя — надо дойти до конца, каждый раз обновляя ответ.

answer = 0
for i in range(len(a)):
    if a[i] > x:
        answer = i + 1   # без break: пусть перезапишется
print(answer)

Разница в одной строке, и перепутать их легко. Признак ошибки: программа стабильно выдаёт номер не с той стороны списка.

Обратите внимание на answer = 0 до цикла. Ноль здесь — не номер, а признак «не нашлось»: номера начинаются с единицы, поэтому спутать нельзя. Условие всегда говорит, что выводить, если подходящих нет, — этот случай надо прочитать и обработать.

И ещё: цикл идёт по номерам, а не по значениям. Как только в ответе нужен номер, for x in a не подходит.

Что найдёт этот цикл?

answer = 0
for i in range(len(a)):
    if a[i] > 0:
        answer = i + 1

Задачи про соседей выглядят одинаково, а ломаются всегда на краях.

count = 0
for i in range(1, len(a) - 1):        # без первого и последнего
    if a[i] > a[i - 1] and a[i] > a[i + 1]:
        count += 1

Границы цикла здесь не случайны: у элемента с номером 0 нет соседа слева, у последнего — справа. Возьмёте range(len(a)) — программа упадёт на a[i + 1].

Отдельно проверьте, что будет при одном и двух элементах. При len(a) = 1 третий вариант даёт range(1, 0) — пустой промежуток, цикл не выполнится ни разу, и это верно: локальных максимумов там нет.

Про дроби. Условие «элемент равен среднему соседей» лучше писать без деления: 2 * a[i] == a[i - 1] + a[i + 1]. Деление даёт дробь, а сравнение дробей на равенство — источник неточностей.

Задача: найти наибольшую сумму $k$ подряд идущих элементов.

Прямолинейное решение — для каждого начала посчитать сумму:

for i in range(len(a) - k + 1):
    total = sum(a[i:i + k])           # каждый раз заново

Работает верно, но делает до $n \cdot k$ действий. При $n = 100\,000$ и $k = 50\,000$ это пять миллиардов — не пройдёт.

А между соседними окнами разница крошечная: одно число ушло слева, одно пришло справа. Значит сумму можно не пересчитывать, а поправлять:

total = sum(a[:k])            # первое окно — честно
best = total

for i in range(k, len(a)):
    total += a[i] - a[i - k]  # пришёл новый, ушёл старый
    if total > best:
        best = total

Получается один проход вместо $n \cdot k$ действий. Приём называется скользящим окном и встречается всюду, где надо перебрать все куски одинаковой длины.

Та же идея работает и в задачах про «сумму слева и справа»: вместо пересчёта обеих сумм на каждой позиции держат общую сумму и накапливают левую по ходу.

В списке 10 элементов, длина окна равна 3.

Сколько всего наборов из трёх подряд идущих элементов? Введите целое число.

Выход за границу у соседей. a[i + 1] на последнем шаге. Признак: list index out of range. Лечится границами цикла, а не проверками внутри.

Перепутанные «первый» и «последний». Лишний break или его отсутствие. Признак: ответ верный по значению, но номер не тот.

Квадрат вместо прохода. Для каждого элемента считать что-то по всему списку — «сумму до него», «сколько больше него». На тысяче элементов пройдёт, на ста тысячах нет. Признак: превышение времени при верном ответе на маленьких тестах.

Как проверять себя

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

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Разминочные — про условия и номера, основные — про соседей и характеристики всего списка, со звёздочкой — про окна и накопление по ходу.

В трёх задачах прямолинейное решение верно, но не укладывается в лимит. Ограничения в условии на это указывают: если написано $10^5$, а ваше решение проходит по списку для каждого элемента — оно не пройдёт.

Задача: «дан список из $n$ чисел, $n$ до $10^5$; для каждого элемента посчитайте, сколько элементов слева от него меньше его самого, и выведите наибольшее из этих количеств».

Ученик написал:

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

for i in range(len(a)):
    count = 0
    for j in range(i):
        if a[j] < a[i]:
            count += 1
    if count > best:
        best = count

print(best)

На маленьких тестах ответ верный, на больших — превышение времени. Оцените количество действий, объясните, почему добавление проверок внутрь цикла не поможет, и предложите, в какую сторону думать.