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

Учитывая массив arr размера N , где каждый элемент представляет длину стороны, задача состоит в том, чтобы найти четырехугольник с максимальным периметром, который можно создать, используя стороны в данном массиве. Если четырехугольник не может быть составлен, выведите -1.

Примеры:

Input: arr[ ] = {3, 1, 2, 4, 2, 1}
Output: 11
Explanation: A quadrilateral of perimeter 4 + 3 + 2 + 2 = 11 can be formed which is the maximum possible.

Input: arr[ ] = {1, 1, 2, 2, 20}
Output: 6

Input: arr[ ] = {1, 2, 4, 10}
Output: -1

Подход: Данную задачу можно решить, перебирая все возможные комбинации сторон (a, b, c, d) из заданного массива. Можно заметить, что стороны a, b, c и d образуют действительный четырехугольник, только если сумма трех меньших сторон больше или равна наибольшей стороне, или периметр четырехугольника больше или равен (2 * большая сторона). Поэтому переберите все возможные значения (a, b, c, d) из заданного массива arr[] и проверьте, образует ли он допустимый четырехугольник.

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

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