Tam giác chu vi lớn nhất từ mảng trong C++

Đề bài

Cho mảng số nguyên không âm. Tìm 3 phần tử tạo thành tam giác có chu vi lớn nhất.

Ví dụ

arr = {5, 1, 3, 5, 7, 4} → Chu vi max = 7 + 5 + 5 = 17.

Thuật toán

1. Sắp xếp mảng giảm dần.
2. Duyệt từ đầu, kiểm tra 3 phần tử liên tiếp arr[i], arr[i+1], arr[i+2].
3. Nếu arr[i] < arr[i+1] + arr[i+2] (bất đẳng thức tam giác) → đó là tam giác chu vi lớn nhất (vì mảng đã sắp giảm).

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

int getMaxPerimeter(int *arr, int n) {
    sort(arr, arr + n, greater<int>());
    int maxPerimeter = 0;
    for (int i = 0; i < n - 2; ++i) {
        if (arr[i] < arr[i + 1] + arr[i + 2]) {
            maxPerimeter = arr[i] + arr[i+1] + arr[i+2];
            break; // Tìm thấy ngay do đã sắp giảm
        }
    }
    return maxPerimeter ? maxPerimeter : -1;
}

int main() {
    int arr[] = {5, 1, 3, 5, 7, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int maxPerimeter = getMaxPerimeter(arr, n);
    if (maxPerimeter != -1)
        cout << "Max perimeter = " << maxPerimeter << endl;
    else
        cout << "Triangle formation is not possible" << endl;
    return 0;
}

Kết quả

Max perimeter = 17

Độ phức tạp: O(n log n) do sắp xếp. Chỉ cần kiểm tra O(n) bộ ba liên tiếp sau khi sắp xếp.