Предполагая, что есть хотя бы одна пара элементов, удовлетворяющих условиям, и нет умножения двух элементов в нем, переполняется, это можно сделать за Theta(n-k) время и Theta(1) пространство в наихудшем и лучшем случае, с чем-то вроде этого :
auto back_max = a[0];
auto back_min = a[0];
auto best = a[0]*a[k+1];
for(std::size_t i=1; i<n-(k+1); ++i) {
back_max = std::max(back_max, a[i]);
back_min = std::min(back_min, a[i]);
best = std::min(best, std::min(a[i+k+1]*back_max, a[i+k+1]*back_min));
}
return best;
Это оптимально с точки зрения асимптотики c сложность наихудшего случая как для времени, так и для пространства, поскольку оптимальным произведением может быть a[0] с любым из элементов n-(k+1) на расстоянии не менее k+1, поэтому любой алгоритм, решающий проблему, должен прочитать не менее n-(k+1) целых чисел.
Идея алгоритма заключается в следующем:
Оптимальный продукт использует два элемента a, предположим, что это a[r] и a[s]. Без ограничения общности можно предположить, что s > r, поскольку произведение является коммутативным.
Из-за ограничения abs(s-r) > k это означает, что s >= k+1. Теперь s может быть каждым из индексов, удовлетворяющих этому условию, поэтому мы перебираем эти индексы. Это итерация по i в показанном коде, но для удобства она сдвинута на k+1 (на самом деле не имеет значения). Для каждой итерации нам нужно найти оптимальный продукт, включающий i+k+1 в качестве наибольшего индекса, и сравнить его с предыдущим наилучшим предположением.
Возможные индексы для пары i+k+1 - все индексы меньше или равны i из-за требования расстояния. Нам также нужно было бы повторить все это, но это не является необходимым, поскольку минимум a[i+k+1]*a[j] сверх j при фиксированном i равен min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j])) из-за монотонности продукта (принимая минимум за как для минимума, так и для максимума, превышающего a[j], учитываются два возможных признака a[i+k+1] или, эквивалентно, два возможных направления монотонности.)
Поскольку набор значений a[j], для которых мы оптимизируем здесь, равен просто {a[0], ..., a[i]}, который просто увеличивается на один элемент (a[i]) в каждой итерации i, мы можем просто отслеживать max(a[j]) и min(a[j]) с отдельными переменными, обновляя их, если a[i] больше или меньше, чем предыдущие оптимальные значения. Это делается с помощью back_max и back_min в примере кода.
Первый шаг итерации (i=0) пропускается в l oop и вместо этого выполняется как инициализация переменных.