คำอธิบายปัญหา
กำหนดอาร์เรย์ เราต้องการหาความสูงสูงสุดของสามเหลี่ยมที่เราสามารถสร้างได้ จากค่าในอาร์เรย์ โดยที่ทุกระดับ (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
