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

Опубликовано: 21 Сентября, 2022

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

Примеры:

Input: arr[] = {1, 4, 7, 4}
Output: 3
Explanation: A possible subsets that follow the given conditions are {1, 4, 4} and {4, 4, 7}. The size of both of these subsets is 3 which is the maximum possible.

Input: arr[] = {2, 7, 4, 1, 6, 9, 5, 3}
Output: 4

Подход: Данная проблема может быть решена с помощью жадного подхода с использованием метода скользящего окна. Известно, что для треугольника с длинами сторон A , B и C должно выполняться условие A + B > C , где A и B — стороны с меньшими длинами. Основываясь на вышеприведенном наблюдении, данная проблема может быть решена с помощью следующих шагов:

  • Отсортируйте заданный массив arr[] в порядке неубывания.
  • Сохраните две переменные i и j , где i отслеживает начальную точку текущего окна, а j отслеживает конечную точку текущего окна. Первоначально я = 0 и j = я + 2 .
  • Увеличивайте значение j до тех пор, пока arr[i] + arr[i+1] > arr[j] и следите за максимальным значением j – i в переменной maxSize . Если arr[i] + arr[i+1] > arr[j] , увеличьте значение i на 1 .
  • Выполните описанный выше шаг, пока не будет пройден весь массив.
  • После выполнения вышеуказанных шагов значение, хранящееся в maxSize , является требуемым результатом.

Ниже приведена реализация вышеуказанного подхода:

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

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