C++에서 배열 값의 삼각형 배열의 최대 높이

문제 설명

배열이 주어지면 모든 (i+1) ^th 수준은 이전 수준보다 더 큰 합계를 가진 더 많은 요소를 포함합니다.

예시

입력 배열이 {40, 100, 20, 30}이면 답은 −

피라미드의 맨 아래 수준에는 100과 20이 있고 피라미드의 상위 수준에는 40 또는 30이 있습니다.

알고리즘

우리의 솔루션은 피라미드에 대해 가능한 최대 높이 h가 있는 경우 ( h * (h + 1) ) / 2개의 요소가 배열에 있어야 한다는 논리에 있습니다.

예시

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

출력

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

Result = 2