> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/math/largest-perimeter-triangle.md).

# 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).