Chiều cao tối đa của sự sắp xếp hình tam giác của các giá trị mảng trong C ++

Tuyên bố vấn đề

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

Ví dụ

Nếu mảng đầu vào là {40, 100, 20, 30} thì câu trả lời là 2 là -

Chúng ta có thể có 100 và 20 ở cấp dưới cùng và 40 hoặc 30 ở cấp trên của kim tự tháp

Thuật toán

Giải pháp của chúng tôi chỉ nằm trên logic rằng nếu chúng tôi có chiều cao h tối đa có thể cho kim tự tháp của mình thì (h * (h + 1)) / 2 phần tử phải có trong mảng

Ví dụ

#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) {
         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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Result = 2