Choose a set of side lengths that can form a polygon and has the maximum possible perimeter.
Largest Perimeter Polygon
gfgProblem
You are given an array of positive integers nums, where each value represents the length of a side.
You may choose any non-empty subset of these lengths. Your task is to determine the largest possible perimeter of a polygon that can be formed using the chosen lengths.
A set of side lengths can form a polygon if the longest side is strictly less than the sum of all the other sides.
If no polygon can be formed, return -1.
Notes
- You may use each element at most once.
- The polygon does not need to be regular.
- The perimeter is the sum of all chosen side lengths.
Input Format
- An integer array
numsof positive integers.
Output Format
- Return the maximum possible perimeter of a polygon that can be formed, or
-1if impossible.
Constraints
1 <= nums.lengthnums[i] > 0- Use each side length at most once.
- A valid polygon must satisfy:
maxSide < sum(otherSides).
Example 1
Input
nums = [5, 5, 5]
Output
15
Explanation
All three sides can form a triangle, which is a polygon. The perimeter is 5 + 5 + 5 = 15.
Example 2
Input
nums = [1, 12, 1, 2, 5, 50, 3]
Output
12
Explanation
Using sides [1, 1, 2, 3, 5] gives perimeter 12, and the largest side 5 is less than 1 + 1 + 2 + 3 = 7. Any set including 50 cannot form a polygon with these available sides, so 12 is the maximum.
Show 1 more example
Example 3
Input
nums = [2, 1, 2]
Output
5
Explanation
The three sides form a triangle because 2 < 1 + 2. The perimeter is 5.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.