Given the set of length of triangle, find the Maximum Area Triangle Suppose we are given an array of numbers representing lengths of line segments.  Find which three of these segments can be assembled into a triangle with maximum area.

I can compute the areas of all $O(n^3)$ possible triangles in $O(n^3)$ time using Heron's formula, and then return the largest. Can this be improved to $O(n^2)$ time? Or even faster?
There is an $O(n^2)$ algorithm. By Heron's formula, the area of a triangle whose sides have length $a$, $b$, and $c$ is $S = \frac{1}{4}\sqrt{4a^2b^2 - (a^2+b^2-c^2)^2}$. Thus if we fix $a$ and $b$, the area is maximized when $c$ is closest to $\sqrt{a^2+b^2}$. A simple approach is to try all $O(n^2)$ possible pairs of $a$ and $b$ and perform binary search for the best value of $c$. This approach yields an $O(n^2 \log n)$ algorithm. 

To achieve $O(n^2)$, we first sort the lengths of line segments ($l_1, l_2,\ldots, l_n$) in non-decreasing order. Let $a = l_i$ and $b = l_j$ with $i &lt; j$, and let $k$ be the position in which $l_k$ is closest to $\sqrt{l_i^2 + l_j^2}$. When $j$ runs from $i+1$ to $n$, $k$ also increases gradually to $n$. Thus finding $k$ has an $O(1)$ amortized run time, i.e., the whole algorithm takes $O(n^2)$.

Update 11/26/2013:

An easier $O(n \log n)$ algorithm is to sort $l_i$ in a non-decreasing order, and find  $3\leq k \leq n$ that maximizes the area of the triangle assembled from $l_{k-2}, l_{k-1}$, and $l_{k}$. It follows from the fact that if $i ,j &lt; k$ then $S(l_i, l_j, l_k) \leq S(l_{k-2}, l_{k-1}, l_k)$ (can be proved by taking the derivative of $S$ and that $l_k$ is the length of the longest side).