Algorithms
Medium
2971
3262
Find Polygon With the Largest Perimeter
find-polygon-with-the-largest-perimeter
"""
You are given an array of positive integers nums of length n.
A polygon is a closed plane figure that has at least 3 sides. The longest side of a polygon is smaller than the sum of its other sides.
Conversely, if you have k (k >= 3) positive real numbers a1, a2, a3, ..., ak where a1 <= a2 <= a3 <= ... <= ak and a1 + a2 + a3 + ... + ak-1 > ak, then there always exists a polygon with k sides whose lengths are a1, a2, a3, ..., ak.
The perimeter of a polygon is the sum of lengths of its sides.
Return the largest possible perimeter of a polygon whose sides can be formed from nums, or -1 if it is not possible to create a polygon.

Example 1:

Input: nums = [5,5,5]
Output: 15
Explanation: The only possible polygon that can be made from nums has 3 sides: 5, 5, and 5. The perimeter is 5 + 5 + 5 = 15.

Example 2:

Input: nums = [1,12,1,2,5,50,3]
Output: 12
Explanation: The polygon with the largest perimeter which can be made from nums has 5 sides: 1, 1, 2, 3, and 5. The perimeter is 1 + 1 + 2 + 3 + 5 = 12.
We cannot have a polygon with either 12 or 50 as the longest side because it is not possible to include 2 or more smaller sides that have a greater sum than either of them.
It can be shown that the largest possible perimeter is 12.

Example 3:

Input: nums = [5,5,50]
Output: -1
Explanation: There is no possible way to form a polygon from nums, as a polygon has at least 3 sides and 50 > 5 + 5.


Constraints:

3 <= n <= 105
1 <= nums[i] <= 109
"""
class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        
You are given an array of positive integers nums of length n.
A polygon is a closed plane figure that has at least 3 sides. The longest side of a polygon is smaller than the sum of its other sides.
Conversely, if you have k (k >= 3) positive real numbers a1, a2, a3, ..., ak where a1 <= a2 <= a3 <= ... <= ak and a1 + a2 + a3 + ... + ak-1 > ak, then there always exists a polygon with k sides whose lengths are a1, a2, a3, ..., ak.
The perimeter of a polygon is the sum of lengths of its sides.
Return the largest possible perimeter of a polygon whose sides can be formed from nums, or -1 if it is not possible to create a polygon.

Example 1:

Input: nums = [5,5,5]
Output: 15
Explanation: The only possible polygon that can be made from nums has 3 sides: 5, 5, and 5. The perimeter is 5 + 5 + 5 = 15.

Example 2:

Input: nums = [1,12,1,2,5,50,3]
Output: 12
Explanation: The polygon with the largest perimeter which can be made from nums has 5 sides: 1, 1, 2, 3, and 5. The perimeter is 1 + 1 + 2 + 3 + 5 = 12.
We cannot have a polygon with either 12 or 50 as the longest side because it is not possible to include 2 or more smaller sides that have a greater sum than either of them.
It can be shown that the largest possible perimeter is 12.

Example 3:

Input: nums = [5,5,50]
Output: -1
Explanation: There is no possible way to form a polygon from nums, as a polygon has at least 3 sides and 50 > 5 + 5.


Constraints:

3 <= n <= 105
1 <= nums[i] <= 109


Please complete the code below to solve above prblem:
```python
class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [5,5,5] }
assert my_solution.largestPerimeter(**test_input) == 15

test_input = { "nums": [1,12,1,2,5,50,3] }
assert my_solution.largestPerimeter(**test_input) == 12

test_input = { "nums": [5,5,50] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,1,1] }
assert my_solution.largestPerimeter(**test_input) == 3

test_input = { "nums": [1,1,2] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,1,3] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,1,4] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,1,5] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,2,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,2,2] }
assert my_solution.largestPerimeter(**test_input) == 5

test_input = { "nums": [1,2,3] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,2,4] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,2,5] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,3,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,3,2] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,3,3] }
assert my_solution.largestPerimeter(**test_input) == 7

test_input = { "nums": [1,3,4] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,3,5] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,4,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,4,2] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,4,3] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,4,4] }
assert my_solution.largestPerimeter(**test_input) == 9

test_input = { "nums": [1,4,5] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,5,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,5,2] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,5,3] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,5,4] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [1,5,5] }
assert my_solution.largestPerimeter(**test_input) == 11

test_input = { "nums": [2,1,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,1,2] }
assert my_solution.largestPerimeter(**test_input) == 5

test_input = { "nums": [2,1,3] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,1,4] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,1,5] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,2,1] }
assert my_solution.largestPerimeter(**test_input) == 5

test_input = { "nums": [2,2,2] }
assert my_solution.largestPerimeter(**test_input) == 6

test_input = { "nums": [2,2,3] }
assert my_solution.largestPerimeter(**test_input) == 7

test_input = { "nums": [2,2,4] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,2,5] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,3,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,3,2] }
assert my_solution.largestPerimeter(**test_input) == 7

test_input = { "nums": [2,3,3] }
assert my_solution.largestPerimeter(**test_input) == 8

test_input = { "nums": [2,3,4] }
assert my_solution.largestPerimeter(**test_input) == 9

test_input = { "nums": [2,3,5] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,4,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,4,2] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,4,3] }
assert my_solution.largestPerimeter(**test_input) == 9

test_input = { "nums": [2,4,4] }
assert my_solution.largestPerimeter(**test_input) == 10

test_input = { "nums": [2,4,5] }
assert my_solution.largestPerimeter(**test_input) == 11

test_input = { "nums": [2,5,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,5,2] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,5,3] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [2,5,4] }
assert my_solution.largestPerimeter(**test_input) == 11

test_input = { "nums": [2,5,5] }
assert my_solution.largestPerimeter(**test_input) == 12

test_input = { "nums": [3,1,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [3,1,2] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [3,1,3] }
assert my_solution.largestPerimeter(**test_input) == 7

test_input = { "nums": [3,1,4] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [3,1,5] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [3,2,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [3,2,2] }
assert my_solution.largestPerimeter(**test_input) == 7

test_input = { "nums": [3,2,3] }
assert my_solution.largestPerimeter(**test_input) == 8

test_input = { "nums": [3,2,4] }
assert my_solution.largestPerimeter(**test_input) == 9

test_input = { "nums": [3,2,5] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [3,3,1] }
assert my_solution.largestPerimeter(**test_input) == 7

test_input = { "nums": [3,3,2] }
assert my_solution.largestPerimeter(**test_input) == 8

test_input = { "nums": [3,3,3] }
assert my_solution.largestPerimeter(**test_input) == 9

test_input = { "nums": [3,3,4] }
assert my_solution.largestPerimeter(**test_input) == 10

test_input = { "nums": [3,3,5] }
assert my_solution.largestPerimeter(**test_input) == 11

test_input = { "nums": [3,4,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [3,4,2] }
assert my_solution.largestPerimeter(**test_input) == 9

test_input = { "nums": [3,4,3] }
assert my_solution.largestPerimeter(**test_input) == 10

test_input = { "nums": [3,4,4] }
assert my_solution.largestPerimeter(**test_input) == 11

test_input = { "nums": [3,4,5] }
assert my_solution.largestPerimeter(**test_input) == 12

test_input = { "nums": [3,5,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [3,5,2] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [3,5,3] }
assert my_solution.largestPerimeter(**test_input) == 11

test_input = { "nums": [3,5,4] }
assert my_solution.largestPerimeter(**test_input) == 12

test_input = { "nums": [3,5,5] }
assert my_solution.largestPerimeter(**test_input) == 13

test_input = { "nums": [4,1,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [4,1,2] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [4,1,3] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [4,1,4] }
assert my_solution.largestPerimeter(**test_input) == 9

test_input = { "nums": [4,1,5] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [4,2,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [4,2,2] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [4,2,3] }
assert my_solution.largestPerimeter(**test_input) == 9

test_input = { "nums": [4,2,4] }
assert my_solution.largestPerimeter(**test_input) == 10

test_input = { "nums": [4,2,5] }
assert my_solution.largestPerimeter(**test_input) == 11

test_input = { "nums": [4,3,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [4,3,2] }
assert my_solution.largestPerimeter(**test_input) == 9

test_input = { "nums": [4,3,3] }
assert my_solution.largestPerimeter(**test_input) == 10

test_input = { "nums": [4,3,4] }
assert my_solution.largestPerimeter(**test_input) == 11

test_input = { "nums": [4,3,5] }
assert my_solution.largestPerimeter(**test_input) == 12

test_input = { "nums": [4,4,1] }
assert my_solution.largestPerimeter(**test_input) == 9

test_input = { "nums": [4,4,2] }
assert my_solution.largestPerimeter(**test_input) == 10

test_input = { "nums": [4,4,3] }
assert my_solution.largestPerimeter(**test_input) == 11

test_input = { "nums": [4,4,4] }
assert my_solution.largestPerimeter(**test_input) == 12

test_input = { "nums": [4,4,5] }
assert my_solution.largestPerimeter(**test_input) == 13

test_input = { "nums": [4,5,1] }
assert my_solution.largestPerimeter(**test_input) == -1

test_input = { "nums": [4,5,2] }
assert my_solution.largestPerimeter(**test_input) == 11