Перед сном Рита решила поиграть в игру на телефоне. Дан массив целых чисел, в котором каждый элемент обозначает длину стороны треугольника. Нужно определить максимально возможный периметр треугольника, составленного из сторон с длинами из заданного массива. Помогите Рите скорее закончить игру и пойти спать.
Напомним, что из трёх отрезков с длинами a ≤ b ≤ c можно составить треугольник, если выполнено неравенство треугольника: c < a + b
Разберём пример:
даны длины сторон 6, 3, 3, 2. Попробуем в качестве наибольшей стороны выбрать 6. Неравенство треугольника не может выполниться, так как остались 3, 3, 2 – максимальная сумма из них равна 6.
Без шестёрки оставшиеся три отрезка уже образуют треугольник со сторонами 3, 3, 2. Неравенство выполняется: 3 < 3 + 2. Периметр равен 3 + 3 + 2 = 8.
Формат ввода
В первой строке записано количество отрезков n, 3≤ n≤ 10000.
Во второй строке записано n натуральных чисел, не превосходящих 10 000, – длины отрезков.
Формат вывода
Нужно вывести одно число – наибольший периметр треугольника.
n = int(input())
st = sorted([int(x) for x in input().split()], reverse=True)
for i in range(len(st) - 2):
if st[i] < st[i + 1] + st[i + 2]:
print(st[i] + st[i + 1] + st[i + 2])
break
else:
i += 1