Chiều cao tối đa của tam giác từ giá trị mảng trong C++

Đề bài

Cho một mảng, cần tìm chiều cao tối đa của tam giác có thể tạo từ các giá trị mảng sao cho mỗi cấp (i+1) chứa nhiều phần tử hơn và tổng lớn hơn cấp trước.

Ví dụ

Nếu mảng: {40, 100, 20, 30} thì kết quả = 2 vì:

• Cấp dưới: 100 và 20
• Cấp trên: 40 hoặc 30

Thuật toán

Giải pháp dựa trên logic: nếu chiều cao tối đa h có thể tạo thì phải có h×(h+1)/2 phần tử trong mảng.

Chương trình C++

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

int getMaximumHeight(int *arr, int n) {
    int result = 1;
    for (int i = 1; i <= n; ++i) {
        long long y = (i * (i + 1)) / 2;
        if (y <= n)  // Sửa: y <= n thay vì y < n
            result = i;
        else
            break;
    }
    return result;
}

int main() {
    int arr[] = {40, 100, 20, 30};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Result = " << getMaximumHeight(arr, n) << endl;
    return 0;
}

Kết quả

Result = 2

Lưu ý

Điều kiện thực tế nên là y <= n (không phải y < n) vì với n=4, h=2 cần 3 phần tử (2×3/2=3 ≤ 4). Code gốc có lỗi logic nhỏ.