Задача с HFT компании.

Задача встретилась у одного ученика на собеседование в HFT.
Сразу скажу, задача сложнее, чем Яндекс-задачи.

Дается массив целых чисел a и число k.
Значения подмасива [l, r] будем считать как (r-l+1)*min(a[l], a[l+1], ..., a[r]).
(То есть значения подмасива - это длина массива на минимальное число из подотрезка)

Вы имеете право рассматривать подотрезок [l, r] если l <= k <= r (напомню k дали в инпуте). Найти максимальное значение.

Решение:
Давайте переберем позицию i, и предположим это минимальный элемент какого-то подотрезка.
То есть мы говорим что a[i] минимальное число на каком-то подотрезке [L, R], где L <= k <= R и L <= i <= R.

Значит значения этого подотрезка это a[i] * (R - L + 1). Какие L, R нужно брать для зафиксированного i?
Вам нужно найти минимальный L, и максимальный R что в подотрезке [L, R] число a[i] минимальное.

Если мы для каждой позиции i будем знать L, R то мы сможем найти ответ. Ответ просто max(a[i] * (R[i] - L[i] + 1)), при условии что
L[i] <= k <= R[i].

Теперь поговорим, как же все-таки эти отрезки находить для каждой позиции i.

Эти отрезки мы можем посчитать монотонными стеками. Сначала пройдем слева направо, храня возрастающий монотонный стек.

Когда мы пытаемся добавить число a[i] в стек, мы удаляем сколько-то элементов, замечу, что для этих удаляемых позиций правая граница будет как раз таки i.

То есть мы, когда удаляем число из стека, мы понимаем, что для удаляемого элемента правый отрезок — это i.

Аналогично пройдемся справа налево и посчитаем левые границы.

Решение O(n). Если на собесе решали не за линию то засчитывали фейл.


Код в комментариях.

@algoses