664. The Largest Triangle You Can Build
Given lengths, choose three that form a triangle with a positive area and make the total of the three as large as possible.
Print that total, or 0 when no three lengths form a triangle.
2 1 2 -> 5
1 2 1 -> 0 1 + 1 is not greater than 2
3 2 3 4 -> 10
## Only consecutive triples after sorting
Sort in DECREASING order and walk down, testing each consecutive triple a[i], a[i+1], a[i+2].
The first one that forms a triangle is the answer.
## Why consecutive is enough
Fix the largest side a[i]. Among all pairs below it, the two that most easily satisfy
x + y > a[i] are the two LARGEST, which are a[i+1] and a[i+2]. If even those fail, no pair
under a[i] works and a[i] can be abandoned entirely.
And if they succeed, the total a[i] + a[i+1] + a[i+2] is the largest achievable with a[i] as
the longest side, because the other two are the largest available.
So scanning downwards and stopping at the first success finds the maximum, and nothing further down can beat it: every later triple has a smaller largest side, hence a smaller total.
## Only one inequality to test
With x <= y <= z the conditions x + z > y and y + z > x hold automatically for positive
lengths. Only x + y > z can fail, which is why a single comparison per triple suffices, as in
problem 609.
Equality fails: 1 2 3 is a straight line, not a triangle.
## The relationship with problem 609
609 counts every triple that forms a triangle and sweeps two pointers under a fixed largest side. This wants only the largest total, so the sweep collapses to a single step: the two values immediately below.
Seeing the count version first makes it clear why only the top two matter here.
## Boundaries
Fewer than three lengths answer 0. Lengths that double each time, like 1 2 4 8, answer 0,
since each exceeds the sum of all smaller ones.
## Overflow
Three lengths near 10^9 total 3 * 10^9, which is past the 2147483647 a signed 32
bit integer holds, so the perimeter needs 64 bits.
The pairwise sum inside the comparison is a different figure and a different answer:
a[i+1] + a[i+2] reaches only 2 * 10^9, which FITS. So the test is safe in 32 bits
while the value printed is not. Checking the two separately, rather than widening everything
on the strength of the larger one, is the habit worth taking away.
## Cost
Time O(n log n) for the sort. Space O(1) beyond the input.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ each length ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n positive integers, the lengths.
Output
Print one integer, the largest achievable perimeter, or 0 if no triangle can be formed.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.