Максимальная длина в массиве с условиями
Сегодня прошел вступительный экзамен по алгоритмам и была такая задача
Экологи собрали почасовые данные об изменении температуры воздуха за последние 10 лет. Их интересуют «периоды жары», то есть такие периоды, которые начинались с температуры выше заданного порога жары, например, 30 градусов, и в каждый следующий час температура не опускалась ниже температуры первого часа:
Напишите псевдокод алгоритма, который получает на вход порог жары и массив температур и находит в этом массиве самый длинный "период жары". Считайте, что размер массива температур не более 10^5, а его элементы - целые числа от -91 до +57.
Не важно, что алгоритм не рассматривает какие-то граничные случаи или что код не скомпилируется. Важна идея и реализация алгоритма самого
Мое решение:
Идея такова, что просто прямо по массиву проходимся и с помощью условий проверяем их выполнение и если "период жары" заканчивается, то обновляем максимальную длительность. Его сложность O(n). Но где-то внутри себя я чувствую, что он неправильный, пытаюсь найти такие случаи, которые его сломают, но пока что не получается. Прошу помочь разобраться или найти входные данные, при которых алгоритм некорректен (граничные случаи не рассматривать).
#include <iostream>
#include <vector>
using namespace std;
int main() {
// heat - порог жары
int heat;
vector<int> temperature;
// Чтобы не расписывать ввод данных
cin >> heat >> temperature;
int max_distance, distance = 0;
// Индексы начала и конца максимального "периода жары"
int first_index, last_index = 0;
// Температура первого часа t_i
int first_temperature = temperature[0];
bool flag = false;
for (int hour = 0; hour < temperature.size(); ++hour) {
if (temperature[hour] > heat && flag == false) {
flag = true;
first_temperature = temperature[hour];
first_index = hour;
continue;
}
if (temperature[hour] >= first_temperature && flag == true) {
++distance;
} else {
if (max_distance <= distance) {
max_distance = distance;
last_index = hour;
}
flag = false;
distance, first_index, last_index = 0;
}
cout << distance << " " << first_index << " " << last_index << endl;
return 0;
}
Ответы (1 шт):
Пришли результаты за экзамен. Задача решена почти правильно, ошибка только в индексах, нужно было правильно реализовать начало и конец максимального "периода жары". Сложность O(n)
