给定一个数组,我们需要从数组值中找到可以形成的三角形的最大高度,以使第(i + 1)个级别包含更多元素,而上一个级别的总和更大。
如果输入数组为{40,100,20,30},则答案为2,如-
我们可以在金字塔的最下层有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