Задача в Т-Банк

Василию на день рождения подарили массив билет в кино. Билет был необычный: Василий мог сесть на любое место в зале, на которое захочет. Так как в кино крутили Барби, то весь зал был переполнен, кроме одного ряда. На каждом месте в ряду известно, сидит ли человек или нет. Известно, что в этом ряду сидит хотя бы один человек и свободно хотя бы одно место, чтобы Василий смог сесть.
Василий не любит людей... Он хочет сесть на такое место, чтобы расстояние до ближайшего человека было максимальным. Помогите ему в этом

Дан массив, состоящий из 0 и 1: свободно или занято место соответственно
Верните максимальное расстояние до ближайшего человека из возможных

Решение:
Решается довольно просто за два прохода: сначала посчитаем для i-го сидения ближайшего справа человека, вторым проходом просто считаем ответ: поддерживаем ближайшего слева человека, берем минимум из расстояний и сохраняем ответ.

Не забываем про крайние случаи при преподсчете: для последних сидений может не быть ближайшего справа занятого сидения и для самых левых ближайшего слева. Так как мы берем минимум из расстояний, то можно просто ставить 2n + 1 и -2n-1 в дефолтные значения ближайших правых и левых занятых сидений соответственно.

int maxDistToClosest(vector<int>& seats) {
int n = (int)seats.size();

vector<int> clRight(n);
for (int i = n - 1; i >= 0; --i) {
if (seats[i])
clRight[i] = i;
else {
if (i != n - 1)
clRight[i] = clRight[i + 1];
else clRight[i] = 2 * n + 1;
}
}

int ans = 0, clLeft = -2 * n - 1;
for (int i = 0; i < n; ++i) {
int dist = min(i - clLeft, clRight[i] - i);
ans = max(ans, dist);

if (seats[i])
clLeft = i;
}

return ans;
}

Асимптотика O(N)

@algoses