โปรแกรมค้นหาความยาวของลำดับย่อยฟีโบนักชีที่ยาวที่สุดใน Python

สมมติว่าเรามีหนึ่งลำดับเช่น X_1, X_2, ..., X_n เป็นเหมือนฟีโบนักชีถ้า -

• น>=3

• X_i + X_i+1 =X_i+2 สำหรับ i + 2 ทั้งหมด <=n

ทีนี้ สมมติว่าอาร์เรย์ A ที่เพิ่มขึ้นอย่างเข้มงวดสร้างลำดับ เราต้องหาความยาวของลำดับย่อยคล้ายฟีโบนักชีที่ยาวที่สุดของ A หากไม่มีลำดับดังกล่าว ให้คืนค่า 0

ดังนั้น ถ้าอินพุตเป็นเหมือน A =[1,2,3,4,5,6,7,8] เอาต์พุตจะเป็น 5 เพราะมีลำดับ [1,2,3,5,8] ของ ความยาว 5.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• sA :=ชุดใหม่จากองค์ประกอบของ A

• สุดท้าย :=องค์ประกอบสุดท้ายของ A

• B :=แผนที่ที่มีแต่ละองค์ประกอบอยู่ใน A และความถี่ของพวกมัน

• ดีที่สุด :=0

• สำหรับฉันในขนาด A เหลือ 0 ทำ

  • a :=A[i]

  • สำหรับแต่ละ b ในอาร์เรย์ย่อยของ A[จากดัชนี i+1 ถึงจุดสิ้นสุด] ทำ

    • ค :=a+b

    • ถ้า c มีอยู่ใน sA แล้ว

      • B[a,b] :=1 + B[b,c]

      • ดีที่สุด :=สูงสุดของดีที่สุด และ B[a,b]+2

    • มิฉะนั้นเมื่อ c> สุดท้ายแล้ว

      • ออกจากวง

• ผลตอบแทนดีที่สุด

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

from collections import Counter
def solve(A):
   sA = set(A)
   last = A[-1]
   B = Counter()
   best = 0
   for i in reversed(range(len(A))):
      a = A[i]
      for b in A[i+1:]:
         c = a+b
         if c in sA:
            B[a,b] = 1 + B[b,c]
            best = max(best , B[a,b]+2)
         elif c>last:
            break
   return best

A = [1,2,3,4,5,6,7,8]
print(solve(A))

อินพุต

[1,2,3,4,5,6,7,8]

ผลลัพธ์

5