# 873\. Length of Longest Fibonacci Subsequence

similar: https://hackmd.io/@y56/BkxGyewa9

similar: https://leetcode.com/problems/arithmetic-slices-ii-subsequence/discuss/1455658/C%2B%2BJavaPython-DP-with-Picture-explained-Clean-and-Concise

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        dp = {}  # dp[a, b] is the length of Fibonacci sequence ending with a, b
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                # Iterate over all pairs.
                previous_endpoint_index = i
                this_endpoint_index = j
                previous_number = arr[previous_endpoint_index]  # b
                this_number = arr[this_endpoint_index]  # c
                further_previous_number = this_number - previous_number  # a
                # a, b, c # a + b = c
        
                # dp[a, b] + 1 = dp[b ,c]
                dp[(this_endpoint_index, previous_number)] = dp.get(
                    (previous_endpoint_index, further_previous_number), 1) + 1
                #                                                       ^
                # If no previous sequence, this is the start of a new sequece, length: 2
        longest = max(dp.values())
        return longest if longest >= 3 else 0  # only len>=3 is valid
    
class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        set_arr = set(arr)
        res = 2
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                # Try all starting pairs.
                a, b = arr[i], arr[j]
                length = 2
                while a + b in set_arr:
                    a, b = b, a + b
                    length += 1
                res = max(res, length)
        return res if res > 2 else 0