โปรแกรมหาความยาว Fibonacci subsequence ยาวสุดใน Python

สมมติว่ามีรายการตัวเลขบวกเพิ่มขึ้นเคร่งครัด nums ต้องการหาความยาว subsequence ยาวสุด (ขั้นต่ำ 3) ที่ A[i] = A[i-1] + A[i-2] สำหรับทุก i > 1

ตัวอย่าง: nums = [1,2,3,4,5,6,7,8,9,10,11,12,13,14] ผลลัพธ์ 6 คือ [1,2,3,5,8,13]

ขั้นตอนการแก้ปัญหา

1. A = nums, n = len(A), maxLen = 0
2. S = set(A)
3. วน i จาก 0 ถึง n-1:
   • วน j จาก i+1 ถึง n-1:
     • x = A[j], y = A[i] + A[j], length = 2
     • ขณะ y in S:
       • z = x + y, x = y, y = z, length += 1
       • maxLen = max(maxLen, length)
4. ถ้า maxLen > 2 คืน maxLen มิฉะนั้นคืน 0

ตัวอย่างโค้ด

class Solution:
    def solve(self, nums):
        A = nums
        n = len(A)
        maxLen = 0
        S = set(A)
        for i in range(0, n):
            for j in range(i + 1, n):
                x = A[j]
                y = A[i] + A[j]
                length = 2
                while y in S:
                    z = x + y
                    x = y
                    y = z
                    length += 1
                    maxLen = max(maxLen, length)
        if maxLen > 2:
            return maxLen
        else:
            return 0

ob = Solution()
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
print(ob.solve(nums))

อินพุต

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

เอาต์พุต

6