Ctrl K

Самый большой разрыв по двум рядам

Средняя
Даны два массива целых чисел first и second одинаковой длины. Для пары индексов i и j её разрыв равен |first[i] - first[j]| + |second[i] - second[j]| + |i - j|. Верните наибольший разрыв среди всех пар 0 ≤ i, j < len(first). Перебор всех пар работает за O(n²) — попробуйте найти линейное решение.
Пример 1
first=[3, -1, 4], second=[0, 2, -2] → 10

Пара индексов 1 и 2: |-1 - 4| + |2 - (-2)| + |1 - 2| = 5 + 4 + 1 = 10.

Пример 2
first=[5, 5], second=[7, 7] → 1

Значения совпадают, остаётся только расстояние между индексами: 1.

Ограничения
  • 2 ≤ len(first) == len(second) ≤ 40 000
  • -10⁶ ≤ first[i], second[i] ≤ 10⁶
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПовернуть квадрат по часовой СредняяПостфиксный калькулятор СредняяПрокрутка массива вправо СредняяПростые числа до границы СредняяN-е число из заданных простых Средняя
загружаем Python…
Вход
first=[3, -1, 4], second=[0, 2, -2]
Ожидается
10

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 95 тестов на сервере, включая скрытые.