1. Идея

Нужно найти максимум значения a_j - a_i, где i < j.

Если перебирать все пары дней, получится слишком долго: O(n^2). При n до 2 * 10^5 такой подход не подходит.

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

a[j] - min_pref

где min_pref — минимальная цена на отрезке от первого дня до дня j - 1.

Остаётся во время одного прохода:

• поддерживать минимум на префиксе;
• обновлять ответ.

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

1. Для фиксированного дня продажи j выгоднее всего купить акцию в тот предыдущий день, где цена была минимальной.

2. Поэтому не нужно хранить все предыдущие цены. Достаточно хранить только одно число: минимальную цену среди уже просмотренных дней.

3. Важно, что по условию нужно выбрать именно два разных дня, причём i < j.
   Значит, даже если все разности отрицательные, всё равно нужно вывести наибольшую из них, а не 0.

4. Поэтому начальное значение ответа нельзя ставить равным 0.
   Нужно сразу взять первую допустимую разность: a[1] - a[0].

3. Алгоритм

1. Считываем n и массив a.
2. Пусть:
   • min_pref = a[0] — минимальная цена среди уже пройденных дней;
   • ans = a[1] - a[0] — первая допустимая прибыль.
3. Для каждого j от 1 до n - 1:
   • пробуем продать в день j, тогда прибыль равна a[j] - min_pref;
   • обновляем ans;
   • затем обновляем min_pref = min(min_pref, a[j]).
4. Выводим ans.

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

Докажем, что алгоритм действительно находит максимальное значение a_j - a_i при i < j.

Рассмотрим некоторый день j как день продажи.

К этому моменту min_pref хранит минимальную цену среди дней 0, 1, ..., j - 1. Значит, если продавать в день j, то наилучший день покупки среди всех допустимых предыдущих дней — это именно день с ценой min_pref.

Тогда лучшая прибыль для фиксированного j равна a[j] - min_pref.

Алгоритм перебирает все возможные дни продажи j от 1 до n - 1 и для каждого вычисляет лучшую возможную прибыль. Из всех этих значений берётся максимум, значит в итоге получаем максимум по всем парам i < j.

Почему порядок обновления важен:

• сначала считаем a[j] - min_pref, чтобы покупка происходила раньше продажи;
• только после этого включаем a[j] в префиксный минимум.

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

5. Сложность

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

6. Код на C++17

#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];
    }

    long long min_pref = a[0];
    long long ans = a[1] - a[0];

    for (int j = 1; j < n; j++) {
        ans = max(ans, a[j] - min_pref);
        min_pref = min(min_pref, a[j]);
    }

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

7. Код на Python 3

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

min_pref = a[0]
ans = a[1] - a[0]

for j in range(1, n):
    ans = max(ans, a[j] - min_pref)
    min_pref = min(min_pref, a[j])

print(ans)