คำชี้แจงปัญหา
จากอาร์เรย์ เราต้องหาความสูงสูงสุดของสามเหลี่ยมที่เราสร้างได้ จากค่าอาร์เรย์ที่ทุกๆ (i+1) th ระดับมีองค์ประกอบมากขึ้นโดยมีผลรวมมากขึ้นจากระดับก่อนหน้า
ตัวอย่าง
หากอาร์เรย์อินพุตคือ {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
