然後看主算法。妳的算法是O(n ^ 3)。對於n=100000的數據,肯定是嚴重超時。
對於n=100000的數據,必須用O(nlogn)以下的算法求解。這個問題是貪,不是搜。
談談想法。
從最大到最小排序,然後取最大的三條邊來判斷三角形的條件。如果沒有,用第二、第三、第四邊來判斷;如果沒有,用第三、第四、第五邊來判斷。什麽時候可以?三邊之和就是最大周長。
證明:
假設我有壹個數組a[0...n-1]按從大到小的順序排列。對於最大的三條邊,如妳所說,這裏判斷三角形的唯壹條件是A [0]