У меня есть массив из нескольких миллионов чисел.
double* const data = new double (3600000);
Мне нужно выполнить итерацию по массиву и найти диапазон (наибольшее значение в массиве минус наименьшее значение). Однако есть улов. Я только хочу найти диапазон, где наименьшие и наибольшие значения находятся в пределах 1000 выборок друг друга.
Поэтому мне нужно найти максимум: диапазон (данные + 0, данные + 1000), диапазон (данные + 1, данные + 1001), диапазон (данные + 2, данные + 1002),...., (данные + 3599000, данные + 3600000).
Надеюсь, это имеет смысл. В принципе, я мог бы сделать это, как описано выше, но я ищу более эффективный алгоритм, если он существует. Я думаю, что вышеупомянутый алгоритм O (n), но я чувствую, что его можно оптимизировать. Идея, с которой я играю, состоит в том, чтобы следить за последними максимумами и минимумами и как далеко назад, а затем только отступать, когда это необходимо.
Я буду кодировать это на С++, но хороший алгоритм в псевдокоде будет просто прекрасен. Кроме того, если этот номер, который я пытаюсь найти, имеет имя, мне бы хотелось узнать, что это такое.
Спасибо.