# Largest Perimeter Triangle

[https://leetcode.com/problems/largest-perimeter-triangle/](https://leetcode.com/problems/largest-perimeter-triangle/)

> Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.
>
> If it is impossible to form any triangle of non-zero area, return 0.

## Thoughts

1. 三角形周长最大，也就是尽量让三条边大，并且满足任意两条边大于第三条边。
2. 因为要比大小，先排序。从大到小遍历，假定已经遍历到了i并把它作为一条边, 因为要找两条边和大于i的，则只能是剩下中的两条最大边i-1和i-2作为剩下两条边。验证i-1和i-2的和是否大于i, 满足则i, i-1和i-2即所求。

```
class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        sort(A.begin(), A.end());
        for (int i = A.size() - 1; i >= 2; --i) {
            if ((A[i - 2] + A[i - 1]) > A[i]) return A[i] + A[i - 1] + A[i - 2];
        }
        return 0;
    }
};
```

## Analysis

时间复杂度O(NlgN).
