สมมติว่าเรามีอาร์เรย์ nums ของความยาวบวก เราต้องหาเส้นรอบรูปสามเหลี่ยมมากที่สุด โดยเลือก 3 ค่าจากอาร์เรย์ ถ้าไม่สามารถสร้างสามเหลี่ยมพื้นที่ไม่ศูนย์ได้ ให้คืน 0
เช่น [8,3,6,4,2,5] ผลลัพธ์คือ 19
ขั้นตอนการแก้ปัญหา
- เรียง nums จากน้อยไปมาก
- a = pop ตัวสุดท้าย (มากที่สุด), b = pop ตัวถัดไป, c = pop ตัวถัดไป
- while b + c ≤ a:
- ถ้า nums ว่าง: คืน 0
- a = b, b = c, c = pop ตัวสุดท้ายจาก nums
- คืน a + b + c
เหตุผล: สามเหลี่ยมต้องมีผลรวมสองด้านสั้นกว่าด้านยาว (b + c > a) เริ่มจาก 3 ค่ามากที่สุด แล้วเลื่อนลงมาเรื่อยๆ จนกว่าจะเป็นสามเหลี่ยมได้
ตัวอย่างโค้ด
def solve(nums):
nums.sort()
a, b, c = nums.pop(), nums.pop(), nums.pop()
while b + c <= a:
if not nums:
return 0
a, b, c = b, c, nums.pop()
return a + b + c
nums = [8,3,6,4,2,5]
print(solve(nums))
ข้อมูลเข้า
[8,3,6,4,2,5]
ข้อมูลออก
19
