Given an array of positive integers arr[] of length n, the task is to find the largest possible perimeter of a polygon whose sides can be formed from the elements in arr. If it is not possible to create a polygon, return -1. A polygon has at least 3 sides, and the longest side of a polygon must be smaller than the sum of the other sides. The perimeter of a polygon is the sum of the lengths of its sides.

Examples:

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

Input: arr = [1, 12, 1, 2, 5, 50, 3]
Output: 12
Explanation: The polygon with the largest perimeter that can be made from arr has 5 sides: 1, 1, 2, 3, and 5. The perimeter is 1 + 1 + 2 + 3 + 5 = 12.

Approach:

To find the largest possible perimeter of a polygon from a given array of positive integers, we need to ensure that the polygon’s sides satisfy the triangle inequality property: the sum of any two sides must be greater than the third side. The most efficient way to achieve this is by sorting the array in non-decreasing order. By doing so, we can systematically check from the largest to the smallest elements to find the largest valid polygon. We iterate from the end of the sorted array, maintaining the sum of the elements excluding the current one, and check if this sum is greater than the current element (which would be the longest side of the polygon). If this condition is satisfied, we return the sum of these elements as the perimeter. If no valid polygon can be formed, we return -1.

Step-by-Step Approach

• Sort the array in non-decreasing order. This helps in easily checking the triangle inequality property by considering the largest elements first.
• Compute the total sum of the array elements. This sum will be adjusted as we iterate through the array.
• Start iterating from the end of the sorted array (i.e., the largest elements).
  • For each element, decrement the total sum by the current element (consider this as excluding the current element from the possible polygon sides).
  • Check Triangle Inequality:
    • For each element considered as the longest side, check if the remaining total sum (sum of other sides) is greater than the current element.
    • If this condition is met, return the sum of the current element and the remaining total sum as the largest perimeter.
• If no valid polygon can be formed after checking all possible sides, return -1.

Below is the implementation of the above approach:

#include <bits/stdc++.h>
using namespace std;

long long largestPerimeter(vector<int>& nums)
{
    // Step 1: Sort the array
    sort(nums.begin(), nums.end());

    // Step 2: Calculate the total sum of the array
    long long totalSum
        = accumulate(nums.begin(), nums.end(), 0LL);

    // Step 3: Iterate from the end of the array
    for (int i = nums.size() - 1; i >= 2; i--) {
        // Step 4: Adjust total sum by excluding the current
        // element
        totalSum -= nums[i];

        // Step 5: Check triangle inequality
        if (totalSum > nums[i])
            return totalSum + nums[i];
    }

    // Step 6: Return -1 if no valid polygon can be formed
    return -1;
}

int main()
{
    // Example 1
    vector<int> nums1 = {1, 12, 1, 2, 5, 50, 3};
    cout << largestPerimeter(nums1) << endl;

    return 0;
}

import java.util.*;

public class LargestPerimeter {

    public static long largestPerimeter(List<Integer> nums) {
        // Step 1: Sort the list
        Collections.sort(nums);

        // Step 2: Calculate the total sum of the list
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        // Step 3: Iterate from the end of the list
        for (int i = nums.size() - 1; i >= 2; i--) {
            // Step 4: Adjust total sum by excluding the current element
            totalSum -= nums.get(i);

            // Step 5: Check triangle inequality
            if (totalSum > nums.get(i)) {
                return totalSum + nums.get(i);
            }
        }

        // Step 6: Return -1 if no valid polygon can be formed
        return -1;
    }

    public static void main(String[] args) {
        // Example 1
        List<Integer> nums1 = Arrays.asList(1, 12, 1, 2, 5, 50, 3);
        System.out.println(largestPerimeter(nums1));
    }
}

// This code is contributed by Shivam Gupta

12

Time Complexity: O(n logn) due to the sorting step.
Auxiliary Space: O(1)