[C Programming] 三角形最大周長問題

題目:
有n支棒子，棒子i的長度是ai。
您想從這些棒子中選出三支來做出周長最長的三角形。
請求出能夠做出的最大周長。如果無法做出三角形時請輸出0。

限制條件:
3 ≦ n ≦ 100, 1 ≦ ai ≦ 10^6

暴力法要花O(n^3)的時間。程式碼大概長這樣：(ary是存放的array)

// O(n^3) algorithm.
int ai,aj,ak,aans;
aans = 0;
for(ai = 0; ai < n; ai++){
 for(aj = ai + 1; aj < n; aj++){
  for(ak = aj + 1; ak < n; ak++){
   int len = ary[ai] + ary[aj] + ary[ak];
   int ma = max(ary[ai], max(ary[aj], ary[ak]));
   int rest = len - ma;
   if(ma < rest) aans = max(aans, len);
  }
 }
}
printf("最大周長：%d\n", aans);

其實有O(n log n)的解法，但書裡面叫我自己想。(靠= =)
在繞了大圈子以後總算想到了。
解法:
1. 先由小到大排序(正常的演算法可以輕鬆達到O(n log n))
2. 設三根分別是第c、b、a根。當c被選定時，
    若存在b、a使三角形成立，
    那麼c、c-1、c-2的組合一定是這當中能達到最大周長的。
    反過來說，如果c、c-1、c-2的組合無法構成三角形，
    那更小的b、a也不可能構成三角形。
    所以對每個c來說考慮c、c-1、c-2的組合就好了。
3. ∵  a(c) + a(c-1) + a(c-2) ≧ a(c-1) + a(c-2) + a(c-3)
    ∴ 讓c從最大的n開始往下，那麼最先找到的三角形必定是周長最大的。
 
4. 一旦找到三角形成立就可以直接輸出。
    如果找到第三根都沒有構成三角形，就輸出0。
5. 這個迴圈只要O(n)，所以整體複雜度決定在排序法的複雜度。

Code大概長這樣：

// Complexity is O(n)
void searchC(int* ary){
    pmeter = 0;
    for(c = n - 1; c >= 2; c--){
        // b=c-1; a=c-2;
        if( (ary[c] - ary[c-1]) < ary[c-2]){
           pmeter = ary[c] + ary[c-1] + ary[c-2]; return;
        }
    }
}

呼叫前不要忘記要先排序array：(當然認真來說quicksort的worst case是O(n^2)...... )

// comparator
int sort(const void *x, const void *y){
 return (*(int*)x - *(int*)y); 
}

// 程式中使用C內建的quicksort
// 請記得#include <stdlib.h>
qsort(ary, n, sizeof(int), sort);