Это одна из задач средней сложности в разделе Жадные алгоритмы набора задач Hackerrank для подготовки к собеседованию. Ссылка здесь.

В задаче указано, что задан массив целых чисел arr и целое число k . Вам нужно создать подмассив arr длины k такой, что

MAX(subarray)-MIN(subarray)свернуто.

Решение

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

Поскольку у нас есть отсортированный массив, минимальное и максимальное значение любого подмассива длины k будет первым и последним элементом. Мы ищем все такие пары в массиве и возвращаем минимальную разницу.

Код

Ссылка на решение Github

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;
}