給定一組三角形的長度，找到最大面積三角形

Question

有一個數組包含三角形的可能長度。找出哪三個長度可以建立最大的三角形。

我可以計算所有可能的三角形區域（Heron公式）來找到最大值，但運行時間很糟糕。如何設計一個運行時間爲（n * n）的算法？

Answer 1

我相信你可以在線性時間內解決這個問題，不同之處在於你必須首先排序你的三角形長度集合，即O（nlogn）。

下面是我該怎麼做。

僞代碼：

// V is the set of length of triangle. 

Order(V) 

// Heron Formula 
define A(a,b,c) = SQRT(4a^2*b^2 - (a^2 + b^2 - c^2) ^2)/4 

// I is the last position in V 
I := V.length - 1 

// T(I) is the area of Maximum Area Triangle 
T(I) = 
if V[I]^2 <= V[I-1]^2+V[I-2]ˆ2 
    then return A(V[I-2],V[I-1],V[I]) 
else 
    return MAX(A(V[I-2],V[I-1],V[I]), T(I-1)) 

說明： 假設C> = B> = A，當c^2 < = A^2 + B^2，如果增加任何變量（ a，b或c），您將擁有一個面積較大的三角形。因此，如果您對三個最大的數字進行峯化，並且等式c^2 < = a^2 + b^2是正確的，那意味着您找到了最大的區域。但是，如果c^2 < = a^2 + b^2不是真的，那就是c^2> a^2 + b^2，比具有不同設置的三角形可能具有更大的面積。如果我們改變b或a的值較低，我們是否會有較低的面積，所以這不是一個選項。所以，我們唯一的選擇是爲c選擇一個diferente值，即T（I-1），這也是一個遞歸。 A（V [I-2]，V [I-1]，V [I]）和T（I-1）之間的最大值將成爲您的答案。