Maximum Perimeter Triangle

Solutions

The problem requires to recall the Triangle inequality:

for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side

So it’s just the matter of sorting the sticks in descending order (since we want the maximum perimeter) and check for each triple of adjacent sticks if the inequality is verified:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


int n;
cin >> n;
vector<int> v(n);
copy_n(istream_iterator<int>(cin), n, begin(v));
sort(begin(v), end(v), greater<>{});
for (auto i=0; i<n-2; ++i)
{
    if (v[i+2] + v[i+1] > v[i])
    {
        cout << v[i+2] << " " << v[i+1] << " " << v[i];
        return 0;
    }
}
cout << -1;

The final cost is \( O(N \cdot log N) \).

Here is a fluent solution in Python:

1
2
3
4


def maximumPerimeterTriangle(sticks):
    sticks = sorted(sticks, reverse=True)
    sticks = zip(sticks, sticks[1:], sticks[2:])
    return next( ([x3,x2,x1] for (x1,x2,x3) in sticks if x3+x2>x1), [-1])