Это одна из задач средней сложности в разделе Жадные алгоритмы набора задач Hackerrank для подготовки к собеседованию. Ссылка здесь.
В задаче указано, что задан массив целых чисел arr
и целое число k
. Вам нужно создать подмассив arr
длины k такой, что
MAX(subarray)-MIN(subarray)
свернуто.
Решение
Для решения этой задачи нет необходимости генерировать все подмассивы. Это было бы решением грубой силы, и мы можем сделать намного лучше, чем это. Вместо этого мы сортируем в порядке убывания и ищем пары, минимизирующие разницу.
Поскольку у нас есть отсортированный массив, минимальное и максимальное значение любого подмассива длины k будет первым и последним элементом. Мы ищем все такие пары в массиве и возвращаем минимальную разницу.
Код
static bool sortFn(int a, int b){return a < b;} static int diff = INT_MAX; int maxMin(int k, vector<int> arr) { sort(arr.begin(), arr.end(), sortFn); for(int i = 0; i <= arr.size()-k; i++) diff = min(arr[i+k-1]-arr[i], diff); return diff; }