1. Идея

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

Самый прямой способ: идти слева направо и хранить текущий максимум cur.

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

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

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

1. Ответ для позиции i зависит только от элементов a[0], a[1], ..., a[i].

2. Если мы уже знаем максимум на первых i - 1 элементах, то для позиции i не нужно пересчитывать всё заново:

   • новый максимум равен либо старому максимуму,
   • либо текущему элементу, если он больше.

3. Поэтому задачу можно решить за один проход по массиву.

Пример для массива 3 1 4 1 5:

• после 3: максимум 3
• после 1: максимум остаётся 3
• после 4: максимум становится 4
• после 1: максимум остаётся 4
• после 5: максимум становится 5

Ответ: 3 3 4 4 5.

3. Алгоритм

1. Считать n.
2. Считать последовательность.
3. Создать массив ответа ans.
4. Взять первый элемент как текущий максимум cur.
5. Добавить cur в ans.
6. Для каждой следующей позиции:
   • если текущий элемент больше cur, присвоить cur = элемент;
   • добавить cur в ans.
7. Вывести массив ans.

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

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

Будем рассматривать элементы слева направо.

• Для первой позиции всё верно: максимум среди одного элемента равен самому этому элементу.
• Пусть после обработки позиции i - 1 переменная cur хранит максимум среди элементов от 0 до i - 1.
• Тогда для позиции i максимум среди элементов от 0 до i может быть только:
  • прежним максимумом cur, если a[i] не больше него;
  • новым элементом a[i], если он больше cur.

Именно это и делает алгоритм:

• сравнивает a[i] и cur,
• при необходимости обновляет cur,
• записывает получившееся значение в ответ.

Значит, после каждого шага в 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> ans;
    ans.reserve(n);

    long long cur;
    cin >> cur;
    ans.push_back(cur);

    for (int i = 1; i < n; i++) {
        long long x;
        cin >> x;
        if (x > cur) cur = x;
        ans.push_back(cur);
    }

    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

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

ans = []
cur = a[0]
ans.append(cur)

for i in range(1, n):
    if a[i] > cur:
        cur = a[i]
    ans.append(cur)

print(*ans)