Самая длинная подпоследовательность с разницей между max и min не более K

Опубликовано: 25 Февраля, 2023

Для заданного массива arr[] размера N и неотрицательного целого числа K задача состоит в том, чтобы найти длину самой длинной подпоследовательности, при которой разница между максимумом и минимумом подпоследовательности не превышает K.

Примеры :

Input: arr[] = {1, 3, 5, 4, 2}, N = 5, K = 3
Output: 4
Explanation: If we consider, the sequence {1, 3, 4, 2}. The subsequence maximum element is 4 and minimum element is 1 and their absolute difference is 3. So maximum length among all subsequence is 4.

Input: arr[] = {5, 5, 5, 5, 5}, N = 5, K = 1
Output: 5

Наивный подход: самый простой способ — сгенерировать все возможные подпоследовательности и найти среди них самую длинную, имеющую разность между максимумом и минимумом не более K.

Временная сложность: O(N * 2 N )
Вспомогательное пространство: O(N)

Эффективный подход : проблему можно эффективно решить с помощью сортировки, основанной на следующей идее:

If we sort the array we can get the elements in sorted order. Now the task reduces to finding the longest window such that the difference between the last and first element of the window is at most K. This can be solved using two pointer technique.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Отсортируйте массив arr[] по возрастанию.
  • Initialize, i = 0 , j = 0 для реализации подхода с двумя указателями и MaxSize = 0 для хранения длины самой длинной подпоследовательности.
  • Запустите цикл до j < N :
    • Если (arr[j] – arr[i]) ≤ K [Поскольку массив отсортирован таким образом, что arr[j] является максимальным, а arr[i] минимальным], обновите MaxSize, чтобы он имел максимальную длину, и приращение j на 1.
    • В противном случае увеличьте i на 1.
  • Возвратите MaxSize как требуемую максимальную длину.

Ниже приведена реализация описанного выше подхода.

Временная сложность : O (N * log N)
Вспомогательное пространство : O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ