Question

С каждым днем приближается зима и Макс измеряет температуру за окном уже​ N​ дней подряд, ежедневно записывая в тетрадь температуру​. Максу стало интересно, какой максимальный перепад температур был в любом непрерывном отрезке, состоящем из​ K​ дней. Перепадом температур Макс считает разность максимальной и минимальной температуры. Помогите Максу найти ответ на вопрос.Входные данныеПервая строка содержит целые числа​N и K— соответственно количество дней в которые Макс делал замеры температуры и количество дней в отрезке.Вторая строка содержит​N целых чисел​ — температура в каждый из дней.Выходные данныеВыведите одно целое число — максимальный перепад температур, который присутствовал в любом отрезке из​ K дней.Примеры:входные данные5 3-5 2 6 1 7выходные данные11входные данные5 2-10 2 5 -20 1выходные данные25От автора: просто перебор всех отрезков не помогает, время ограничено.Желательно, решение на питоне.​

Answer 1

Что-то маловато баллов для такой задачи, ну ладно.  Задачу можно решить за линию следующим образом

Answer 2

Для решения этой задачи, нам нужно найти максимальный перепад температур в любом непрерывном отрезке из K дней.

Мы можем использовать подход, основанный на двух указателях (sliding window technique), чтобы эффективно решить эту задачу.

Вот как это можно сделать на Python:

def find_max_temperature_difference(N, K, temperatures):
    max_difference = float('-inf')
    left = 0
    right = 0
    window_temperatures = []

while right < N:
        window_temperatures.append(temperatures[right])
        if right - left + 1 == K:
            max_temp = max(window_temperatures)
            min_temp = min(window_temperatures)
            max_difference = max(max_difference, max_temp - min_temp)
            window_temperatures.remove(temperatures[left])
            left += 1
        right += 1

return max_difference

# Примеры использования:
temperatures1 = [-5, 2, 6, 1, 7]
result1 = find_max_temperature_difference(5, 3, temperatures1)
print(result1)  # Вывод: 11

temperatures2 = [-10, 2, 5, -20, 1]
result2 = find_max_temperature_difference(5, 2, temperatures2)
print(result2)  # Вывод: 25

В этом коде мы создаем функцию `find_max_temperature_difference`, которая принимает на вход количество дней `N`, количество дней в отрезке `K` и список температур `temperatures`. Мы инициализируем переменные `max_difference`, `left`, и `right`.

Мы используем цикл `while` для обработки каждого дня. Мы добавляем текущую температуру в `window_temperatures` и проверяем, если длина окна достигла `K`. Если это так, мы находим максимальную и минимальную температуры в окне и обновляем `max_difference` при необходимости. Затем мы удаляем самую левую температуру из окна и увеличиваем `left` на 1.

Мы также увеличиваем `right` на 1 для обработки следующего дня. Когда мы обработаем все дни, функция вернет `max_difference`.

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