A sequence X_1, X_2, ..., X_n is fibonacci-like if:

n >= 3
X_i + X_{i+1} = X_{i+2} for all i + 2 <= n

Given a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A.  If one does not exist, return 0.
(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, without changing the order of the remaining elements.  For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].)
 


Example 1:
Input: [1,2,3,4,5,6,7,8]
Output: 5
Explanation:
The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:
Input: [1,3,7,11,12,14,18]
Output: 3
Explanation:
The longest subsequence that is fibonacci-like:
[1,11,12], [3,11,14] or [7,11,18].

 
Note:

3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
(The time limit has been reduced by 50% for submissions in Java, C, and C++.)

Difficulty: interview

Starter code:

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        

Solutions:
class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        def getFS(x1, x2):
            F = [x1, x2]
            while F[-1] <= 1000000000:
                F.append(F[-2] + F[-1])
            return F

        C1 = getFS(1, 0)
        C2 = C1[1:]
        
        def getLLFS(x1, x2):
            max_len = 2
            F = [x1, x2]
            xi = x1 + x2
            while xi in setA: 
                max_len += 1
                F.append(xi)
                xi = F[-2] + F[-1]
            if max_len == 6:
                print(F)
            return max_len
        
        max_len = 2
        setA = set(A)
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                x1, x2 = A[i], A[j]
                
                # calculate X_{max_len+1}
                if x1 * C1[max_len] + x2 * C2[max_len] > A[-1]:
                    break
                max_len = max(max_len, getLLFS(x1, x2))
                
        if max_len < 3:
            return 0
        return max_len
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        n=len(A)
        nums_on_left=set()
        max_seq_len=collections.defaultdict(lambda:2)
        ans=0
        
        for i,c in enumerate(A):
            for j in range(i-1,0,-1):
                b=A[j]
                a=c-b
                if a>=b:
                    break
                if a in nums_on_left:
                    max_seq_len[b,c]=max_seq_len[a,b]+1
                    ans=max(ans,max_seq_len[b,c])
            
            nums_on_left.add(c)
        
        return ans

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {x: i for i, x in enumerate(A)}
        longest = collections.defaultdict(lambda: 2)

        ans = 0
        for k, c in enumerate(A):
            for j in range(k-1, k//2-2, -1):
                i = index.get(c - A[j], None)
                if i is not None and i < j:
                    cand = longest[j, k] = longest[i, j] + 1
                    ans = max(ans, cand)

        return ans if ans >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, array: List[int]) -> int:
        if len(array)<3:
            return len(array)
        d={}
        ans=0
        dp=[[2 for i in range(len(array))] for j in range(len(array))]
        for i in range(len(array)):
            d[array[i]]=i
        for i in range(len(array)-1):
            for j in range(i+1,len(array)):
                if array[i]+array[j] in d:
                    dp[j][d[array[i]+array[j]]]=1+dp[i][j]
                    if dp[j][d[array[i]+array[j]]]>ans:
                        ans=dp[j][d[array[i]+array[j]]]
        return ans


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dp = collections.defaultdict(lambda: 2)
        a = set(A)
        for j in range(2, len(A)):
            for i in range(j):
                if A[j] - A[i] < A[i] and A[j] - A[i] in a:
                    dp[(A[i], A[j])] = dp[(A[j] - A[i], A[i])] + 1
        return max(dp.values() or [0])

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        indexes = {A[0]: 0}
        n = len(A)
        
        dp = [[2 for i in range(n)] for j in range(n)]
        
        max_len = 2
        
        
        for i in range(1, n-1):
            indexes[A[i]] = i
            for j in range(i+1, n):
                diff = A[j] - A[i]
                if diff in indexes:
                    dp[i][j] = 1 + dp[indexes[diff]][i]
                    max_len = max(max_len, dp[i][j])
        
        if max_len > 2:
            return max_len
        return 0
                
        
        
        
        
        
        
        
        
        
        
        
#         dp[i, j] = length of fib seq that ends with i, j
        
        
        
#         [1,3,7,11,12,14,18]


class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        dic = {arr[i]:i for i in range(n)}
        ans = 2
        dp = [[2]*n for _ in range(n)]
        
        for k in range(n):
            for j in range(k):
                i = dic.get(arr[k]-arr[j], None)
                if i is not None and j > i:
                    dp[j][k] = dp[i][j]+1
                    ans = max(ans, dp[j][k])
        if ans == 2:
            return 0
        return ans

class Solution(object):
    def lenLongestFibSubseq(self, A):
        index = {x: i for i, x in enumerate(A)}
        longest = collections.defaultdict(lambda: 2)

        ans = 0
        for k, z in enumerate(A):
            for j in range(k):
                i = index.get(z - A[j], None)
                if i is not None and i < j:
                    cand = longest[j, k] = longest[i, j] + 1
                    ans = max(ans, cand)

        return ans if ans >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        if not A or len(A) == 0:
            return 0
        
        n = len(A)
        
        dp = [[0] * n for _ in range(n)]
        res = 0
        
        for i in range(2, n):
            l = 0
            r = i - 1
            while l < r:
                sum_ = A[l] + A[r]
                if sum_ > A[i]:
                    r -= 1
                elif sum_ < A[i]:
                    l += 1
                else:
                    dp[r][i] = dp[l][r] + 1
                    res = max(res, dp[r][i])
                    l += 1
                    r -= 1
        if res == 0:
            return 0
        return res + 2

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        longest=0
        
        ss=set(A)
        for i,x in enumerate(A):
            for j,y in enumerate(A[i+1:]):
                tmp=x+y
                if(tmp in ss):
                    counter=2
                    t=x
                    while(True):
                        if(t+y in ss):
                            t,y=y,t+y 
                            counter+=1
                        else:
                            break
                    if(longest<counter):
                        longest=counter
        return longest
        
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index_dict={}
        for index,item in enumerate(A):
            index_dict[item]=index
        longest=collections.defaultdict(lambda:2)
        
        res=0
        for index,value in enumerate(A):
            for j in range(index):
                i=index_dict.get(value-A[j],None)
                if(i is not None and i<j):
                    longest[j,index]=longest[i,j]+1
                    res=max(longest[j,index],res)
        if(res<3):
            res=0
        return res 


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {x: i for i, x in enumerate(A)}
        longest = collections.defaultdict(lambda:2)
        
        ans = 0
        for i, a in enumerate(A):
            for j in range(i):
                k = index.get(a - A[j], None)
                if k is not None and k < j:
                    cand = longest[j, i] = longest[k, j] + 1
                    ans = max(cand, ans)
        
        return ans


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {x: i for i, x in enumerate(A)}
        longest = collections.defaultdict(lambda: 2)

        ans = 0
        for k, c in enumerate(A):
            for j in range(k-1, -1, -1):
                if A[j] <= c//2: break
                i = index.get(c - A[j], None)
                if i is not None:
                    cand = longest[A[j], c] = longest[A[i], A[j]] + 1
                    ans = max(ans, cand)
        return ans if ans >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        d = dict()
        for i in range(len(A)):
            for j in range(i):
                if A[i] < 2 * A[j] and A[i] - A[j] in s:
                    d[(A[i], A[j])] = d.get((A[j], A[i]-A[j]), 2) + 1
                    
        return max(d.values() or [0])

from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        N = len(A)
        idx = {n: i for i, n in enumerate(A)}
        dp = defaultdict(lambda: 2)
        res = 0
        for i in range(N):
            for j in range(i):
                if A[i] - A[j] < A[j] and A[i] - A[j] in idx:
                    dp[A[j], A[i]] = dp[A[i]-A[j], A[j]] + 1
                    res = max(res, dp[A[j], A[i]])
        return res if res > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
#         # Time Complexity: O(N^2)
#         # Space Complesity:  O(NlogM)
        
#         index_mapping = {num:index for index, num in enumerate(A)}
#         memory = collections.defaultdict(lambda: 2)
#         # memory[j, k] = memory[i, j] + 1
#         # memory[i, j] a fibonacci subsequence ending with A[i] A[j]
        
#         # index i, j, k
#         result = 0
#         for k, k_num in enumerate(A):
#             for j in range(k):
#                 i = index_mapping.get(k_num - A[j])
#                 if i is not None and i < j:
#                     # (i, j) can connect to (j, k)
#                     memory[j, k] = memory[i, j] + 1
#                     result = max(memory[j, k] , result)  
        
#         return result if result >=3 else 0  # n >= 3


        # 还是老老实实用array matrix来做memorization好了
        # Time Complexity: O(N^2)
        # Space Complesity:  O(N^2)
        index_mapping = {number:index for index, number in enumerate(A)}
        memory = [[2 for i in range(len(A))] for j in range(len(A))]
        
        max_len = 0
        for k in range(len(A)):
            for j in range(k):
                i_num = A[k] - A[j]
                if i_num in index_mapping and index_mapping[i_num] < j:
                    i = index_mapping[i_num]
                    memory[j][k] = memory[i][j] + 1
                    max_len = max(max_len, memory[j][k] )
        return max_len if max_len >= 3 else 0
                    
        
        
        


class Solution:
    def lenLongestFibSubseq1(self, A: List[int]) -> int:
        '''
        time complexity: O(N^2logM)
        '''
        s = set(A)
        n = len(A)
        res = 2
        
        for i in range(n):
            for j in range(i+1,n):
                a = A[i]
                b = A[j]
                length = 2
                while a+b in s:
                    a,b,length = b,a+b, length +1
                res = max(res,length)
        return res if res >2 else 0
        
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        '''
        dp[i][j] represents the length of fibo sequence ends up with (A[i], A[j])
        '''
        n = len(A)
        res = 2
        map = collections.defaultdict(int)
        for i,v in enumerate(A):
            map[v] = i
        
        dp = [[2 for _ in range(n+1)] for _ in range(n+1)]
        for j in range(n):
            for i in range(j):
                diff = A[j] - A[i]
                if diff in map and map[diff] < i:
                    k = map[diff]
                    dp[i][j] = dp[k][i]+1
                    res = max(res,dp[i][j])
        return res if res >2 else 0


class Solution:
    def lenLongestFibSubseq1(self, A: List[int]) -> int:
        '''
        time complexity: O(N^2logM)
        '''
        s = set(A)
        n = len(A)
        res = 2
        
        for i in range(n):
            for j in range(i+1,n):
                a = A[i]
                b = A[j]
                length = 2
                while a+b in s:
                    a,b,length = b,a+b, length +1
                res = max(res,length)
        return res if res >2 else 0
        
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        '''
        dp[i][j] represents the length of fibo sequence ends up with (A[i], A[j])
        '''
        map = collections.defaultdict(int)
        for i, v in enumerate(A):
            map[v]=i
        n = len(A)
        res = 2
        dp = [[2 for _ in range(n+1)] for _ in range(n+1)]
        for j in range(n):
            for i in range(j):
                diff = A[j]-A[i]
                if diff in map and map[diff] < i:
                    k = map[diff]
                    dp[i][j] = 1+dp[k][i]
                    res = max(dp[i][j],res)
        return res if res > 2 else 0
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        count = 0
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                temp = 2
                a = A[i]
                b = A[j]
                while a+b in s:
                    temp += 1
                    count = max(count, temp)
                    t = a
                    a = b
                    b = t+b
        return count
                    


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        longest=0
        
        ss=set(A)
        for i,x in enumerate(A):
            for j,y in enumerate(A[i+1:]):
                tmp=x+y
                if(tmp in ss):
                    ret=[x,y]
                    t=x
                    while(True):
                        if(t+y in ss):
                            t,y=y,t+y 
                            ret.append(y)
                        else:
                            break
                    if(longest<len(ret)):
                        longest=len(ret)
        return longest
        
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        n = len (A)
        v2i = {v: i for i, v in enumerate (A)}
        dp = [[2] * n for _ in range (0, n)]
        ret = 0
        
        # n1 + n2 = n3
        for n3 in range (2, n):
            for n1 in range (0, n3 - 1):
                diff = A [n3] - A [n1]
                if diff < A [n1]: continue
                n2 = v2i.get (diff, -1)
                if n2 != -1:# and n1 < n2 and n2 < n3:
                    length = dp [n1][n2] + 1
                    if length > dp [n2][n3]:
                        dp [n2][n3] = length
                        ret = max (ret, length)
        return ret
        
        
        
        res=0
        d={x:i for i,x in enumerate(A)}
        n=len(A)
        dp=[[2 for j in range(n)] for i in range(n)]
        for i in range(2,n):
            for j in range(i):
                z=A[i] # = A [n3]
                x=A[j] # = A [n1]
                y=z-x # = diff = A [n3] - A [n1]
                k=d.get(y,-1) # n2
                #x<y<z
                if x<y and k!=-1: # A[n1] < diff
                    dp[i][k]=1+dp[k][j] # dp [n3][n2] = 1 + dp [n2][n1]
                    res=max(res,dp[i][k])
        if res>2:
            return res
        return 0

class Solution:
    # brute-force time O(n^2logm), m是A的最大值,代码在下面
    # 试试机械dp, time O(n^2), space O(n^2)
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        M = [[-1 for i in range(n)] for i in range(n)]
        mapping = {v:i for i, v in enumerate(A)}
        ret = 0
        
        def dp(prev_, next_):
            if next_ == n-1:
                return 1
            
            if M[prev_][next_] != -1:
                return M[prev_][next_]
            
            M[prev_][next_] = 1
            if A[prev_]+A[next_] in mapping:
                M[prev_][next_] += dp(next_, mapping[A[prev_]+A[next_]])
            return M[prev_][next_]
        
        for i in range(n):
            for j in range(i+1, n):
                if A[i]+A[j] in mapping:
                    ret = max(ret, 2+dp(j, mapping[A[i]+A[j]]))
        
        return ret if ret > 2 else 0
#     def lenLongestFibSubseq(self, A: List[int]) -> int:
#         ret = 0
#         n = len(A)
#         mapping = {v:i for i, v in enumerate(A)}
        
        
#         for i in range(n):
#             for j in range(i+1, n):
#                 prev_, next_ = A[j], A[i]+A[j]
#                 length = 2
#                 while next_ in mapping:
#                     length += 1
#                     prev_, next_ = next_, prev_+next_
                
#                 if length > 2:
#                     ret = max(ret, length)
        
#         return ret


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dp = {}
        s = set(A)

        for j, c in enumerate(A):
            for b in A[:j]:
                a = c - b
                if a < b and a in s:
                    dp[b, c] = dp.get((a, b), 2) + 1

        return max(dp.values() or [0])

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {i:k for k,i in enumerate(A)}
        longest = collections.defaultdict(lambda:2) # ???
        
        ans = 0
        for k,z in enumerate(A):
            for j in range(k):
                i = index.get(z-A[j],None)  # index of z-A[j]
                if i is not None and i<j:
                    longest[j,k] = longest[i,j]+1
                    ans = max(ans, longest[j,k])
        return ans

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {x:i for i, x in enumerate(A)}
        longest = collections.defaultdict(lambda: 2)
        result = 0
        
        for k, z in enumerate(A):
            for j in range(k):
                i = index.get(z-A[j], len(A)+1)
                if i < j:
                    longest[j, k] = longest[i, j] + 1
                    if longest[j, k] > result:
                        result = longest[j, k]
        
        return result if result >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        n = len (A)
        v2i = {v: i for i, v in enumerate (A)}
        dp = [[2] * n for _ in range (0, n)]
        ret = 0
        
        # n1 + n2 = n3
        for n3 in range (2, n):
            for n1 in range (0, n3 - 1):
                diff = A [n3] - A [n1]
                if diff < A [n1]: continue
                n2 = v2i.get (diff, -1)
                if n2 != -1:# and n1 < n2 and n2 < n3:
                    length = dp [n1][n2] + 1
                    if length > dp [n2][n3]:
                        dp [n2][n3] = length
                        ret = max (ret, length)
        return ret
        
        


class Solution:
    def lenLongestFibSubseq1(self, A: List[int]) -> int:
        '''
        time complexity: O(N^2logM)
        '''
        s = set(A)
        n = len(A)
        res = 2
        
        for i in range(n):
            for j in range(i+1,n):
                a = A[i]
                b = A[j]
                length = 2
                while a+b in s:
                    a,b,length = b,a+b, length +1
                res = max(res,length)
        return res if res >2 else 0
        
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        '''
        dp[i][j] represents the length of fibo sequence ends up with (A[i], A[j])
        '''
        map = collections.defaultdict(int)
        for i, v in enumerate(A):
            map[v]=i
        n = len(A)
        dp = [[2 for _ in range(n+1)] for _ in range(n+1)]
        for j in range(n):
            for i in range(j):
                diff = A[j]-A[i]
                if diff in map and map[diff] < i:
                    k = map[diff]
                    dp[i][j] = 1+dp[k][i]
        ans = max([max(n) for n in dp])
        return 0 if ans <= 2 else ans
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        def getLength(prev,curr):
            nxt = curr+prev
            if nxt in Aset:
                return 1+getLength(curr,nxt)
            else:
                return 2
        Aset = set(A)
        out = max(max([getLength(a,b) for a in A[:i]],default=float('-inf')) for i,b in enumerate(A))
        return out if out >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        if n < 3:
            return 0
        dp = [[2 for j in range(n)] for i in range(n)]
        ans = 2
        hmap = {A[0]:0, A[1]:1}
        for i in range(2, n):
            for j in range(1, i):
                pos = hmap.get(A[i]-A[j], -1)
                if pos >= 0 and pos < j:
                    dp[i][j] = max(dp[i][j], dp[j][pos]+1)
                    ans = max(ans, dp[i][j])
            hmap[A[i]] = i
        return ans if ans > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        idxs = {x: i for i, x in enumerate(A)}
        longest = defaultdict(lambda: 2)
        
        res = 0
        for k, val in enumerate(A):
            for j in range(k):
                i = idxs.get(val - A[j], None)
                if i is not None and i < j:
                    candidate = longest[(j, k)] = longest[(i, j)] + 1
                    res = max(res, candidate)
        return res if res >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: 'List[int]') -> 'int':
        map = collections.defaultdict(int)
        for i, v in enumerate(A):
            map[v]=i
        n = len(A)
        dp = [[2 for _ in range(n+1)] for _ in range(n+1)]
        for j in range(n):
            for i in range(j):
                diff = A[j]-A[i]
                if diff in map and diff < A[i]:
                    k = map[diff]
                    dp[i][j] = max(dp[i][j], 1+dp[k][i])
        ans = max([max(n) for n in dp])
        return 0 if ans <= 2 else ans

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        N=len(A)
        index={}
        for i in range(N):
            index[A[i]]=i
        dp=[[0]*N for _ in range(N)]
        ans=0
        for i in range(N-1,-1,-1):
            hi=A[i]
            for j in range(i-1,-1,-1):
                lo=A[j]
                if hi-lo<=0 or hi-lo>=lo:
                    break
                if hi-lo in index:
                    ind = index[hi-lo]
                    length = 1+dp[j][i]
                    dp[ind][j]=length
                    ans=max(ans,length)
        return ans+2 if ans>0 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        mp = {}
        
        for v in A:
            mp[v] = set()
        
        result = 0
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                a = A[i]
                b = A[j]
                l = 2
                while True:
                    if b in mp[a]:
                        break
                    if l != 2:
                        mp[a].add(b) 
                    c = a + b
                    if c not in mp:
                        break
                    a, b = b, c
                    l += 1
                if l < 3:
                    l = 0
                else:
                    result = max(result, l)
        return result


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {x: i for i, x in enumerate(A)}
        longest = [[2 for i in range(len(A))] for j in range(len(A))]
        
        ans = 0
        for k, z in enumerate(A):
            for j in range(k):
                i = index.get(z - A[j], None)
                if i is not None and i < j:
                    longest[j][k] = longest[i][j] + 1
                    ans = max(ans, longest[j][k])
        return ans if ans >=3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        d = dict()
        for i in range(2, len(A)):
            for j in range(i):
                if A[i] < 2 * A[j] and A[i] - A[j] in s:
                    d[(A[i], A[j])] = d.get((A[j], A[i]-A[j]), 2) + 1
                    
        return max(d.values() or [0])

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        n = len(A)
        
        
        def getlength(a, b):
            l = 0
            
            temp = a + b
            if temp in s:
                l = 2
            else: return 0
            
            while temp in s:
                temp, b = temp + b, temp
                l += 1
            
            return l
        
        mx = 0
        for i in range(n):
            for j in range(i+1, n):
                ll = getlength(A[i], A[j])
                if mx < ll:
                    mx = ll
        
        return mx

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        Aset = set(A)
        res = 0
        for i in range(len(A)-1):
            for j in range(i+1, len(A)):
                a, b = A[i], A[j]
                temp = 2
                while a+b in Aset:
                    temp += 1
                    a, b = b, a+b
                if temp >= 3:
                    res = max(res, temp)
        return res

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        dp = [{} for i in range(n)]
        result = 0
        for i in range(n):
            for j in range(i):
                prev = A[i] - A[j]
                if prev in dp[j]:
                    l = dp[i][A[j]] = dp[j][prev] + 1
                    result = max(result, l)
                else:
                    dp[i][A[j]] = 2
        return result

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        L = len(A)
        res = 0
        if L<3:
            return 0
        if L==3:
            return 3 if A[0]+A[1]==A[2] else 0
        s = set(A)
        for i in range(2,L):
            for j in range(i):
                L,R = A[j],A[i]
                cur = 2
                while R-L in s and R-L<L:
                    cur += 1
                    L,R = R-L,L
                res = max(res,cur)
                
                #print(A[i],A[j],cur)
        return res if res>2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        set_a = set(A)
        res = 0
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                x, y = A[i], A[j]
                leng = 2
                while x+y in set_a:
                    x, y = y, x+y
                    leng += 1
                res = max(res, leng)
        return res if res >=3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        res = 2
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                a = A[i]
                b = A[j]
                lengthOfSeq = 2
                
                while a + b in s:
                    a, b, lengthOfSeq = b, a + b, lengthOfSeq + 1
                res = max(res,lengthOfSeq)
        return res if res > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        dp = [[2] * n for i in range(n)]
        
        m = dict()
        for i in range(n):
            m[A[i]] = i
            
        ans = 0
        for i in range(n):
            for j in range(i+1, n):
                a_k = A[j] - A[i]
                if a_k > A[i]:
                    break
                k = m.get(a_k, None)
                if k is not None and k < i:
                    dp[i][j] = dp[k][i] + 1
                    ans = max(ans, dp[i][j])
        return ans if ans >= 3 else 0
                
                


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        max_ = 0
        dp = [[0 for i in range(n)] for j in range(n)]
        for i in range(2, n):
            l = 0 
            r = i - 1
            while l < r:
                sum_ = A[l] + A[r]
                if sum_ > A[i]:
                    r -= 1
                elif sum_ < A[i]:
                    l += 1
                else:
                    dp[r][i] = dp[l][r] + 1
                    max_ = max(max_, dp[r][i])
                    r -= 1
                    l += 1
        if max_ == 0:
            return 0
        else:
            return max_ + 2

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        dp = [[2 for _ in range(n)] for _ in range(n)]
        indMap = {x: i for i, x in enumerate(A)}

        for i in range(n):
            for j in range(i+1, n):
                diff = A[j] - A[i]
                if diff in indMap and indMap[diff] < i:
                    k = indMap[diff]
                    dp[i][j] = max(dp[i][j], 1 + dp[k][i])
        
        return max([v for row in dp for v in row if v > 2] or [0])


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        res = 2
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                a, b, l = A[i], A[j], 2
                while a + b in s:
                    a, b, l = b, a + b, l + 1
                res = max(res, l)
        return res if res > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        S = set(A)
        i = 0
        max_len = 0
        while i < len(A)-1:
            j = i + 1
            while j < len(A):
                subSeq = [A[i], A[j]]
                while subSeq[-1] + subSeq[-2] in S:
                    subSeq.append(subSeq[-1]+subSeq[-2])
                    # print(subSeq)
                    if len(subSeq) > max_len:
                        max_len = len(subSeq)
                j += 1
            i += 1
        return max_len
        
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        s = set(A)
        res = 2
        for i in range(n):
            for j in range(i+1, n):
                a, b, l = A[i], A[j], 2
                while a+b in s:
                    a,b,l = b,a+b,l+1
                res = max(res, l)
                
        return res if res > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        dp = [[2 for _ in range(n)] for _ in range(n)]
        indMap = {x: i for i, x in enumerate(A)}

        for i in range(n):
            for j in range(i+1, n):
                diff = A[j] - A[i]
                if diff in indMap and indMap[diff] < i:
                    k = indMap[diff]
                    dp[i][j] = max(dp[i][j], 1 + dp[k][i])
        
        res = 0
        for row in dp:
            for v in row:
                if v > 2:
                    res = max(res, v)
                
        return res


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        d={}
        for i in range(len(A)):
            d[A[i]]=i
        
        ans=0
        for i in range(0,len(A)):
            for j in range(i+1,len(A)):
                y=A[i]+A[j]
                x=A[j]
                l=2
                while y in d and d[y]>j:
                   # print(y,l)
                    z=x+y
                    x=y
                    y=z
                    l+=1
                ans=max(ans,l)
        return ans if ans>=3 else 0
                    
                


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        sA = set(A)
        B = Counter()
        ans = 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] = B[b, c] + 1 # if recording B[b,c], everything is counted 1. We are tracking back like 3+5, 2+3, 1+2. So we want the 1+2 to be counted the most.
                    ans = max(ans, B[a, b] + 2) # [a, b, c] = [1 ,2, 3], B[b, c] = 1
                if c > A[-1]:
                    break # the inner loop needn't continue
        return ans if ans >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        res = 0
        A_dict = {}
        for x in A:
            A_dict[x] = A_dict.get(x,0) + 1
        
        for i in range(len(A)-1):
            for j in range(i+1, len(A)):
                a, b = A[i], A[j]
                c = a + b
                length = 0
                while c in A_dict:
                    length += 1
                    a, b = b, c
                    c = a + b
                res = max(res, length)
                
        return res + 2 if res > 0 else 0
                
                


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        ans = 0
        setA = set(A)
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                temp = 2
                x = A[j]
                y = A[i] + A[j]
                while y in setA:
                    temp += 1
                    x, y = y, x+y
                ans = max(ans, temp)
        
        return ans if ans >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        ''' correct but too slow lol :'(
        l = len(A)
        
        def loop(one: int, two: int, ind: int, length: int) -> int:
            if (ind == l):
                return length
            elif (one + two == A[ind]):
                #print(\"one, two are \" + str(one) + \" \" + str(two))
                return loop(two, A[ind], ind + 1, length + 1)
            else:
                return loop(one, two, ind + 1, length)
        
        maxLen = 0
        
        for i in range(l):
            for j in range(i+1, l):
                c = loop(A[i], A[j], j+1, 0)
                maxLen = max(maxLen, c)
                
        return (maxLen + 2) if maxLen else maxLen
        '''
        
        mySet = set(A)
        maxCount = 0
        l = len(A)
        
        for i in range(l):
            for j in range(i+1, l):
                one = A[i]
                two = A[j]
                count = 0
                while(one + two) in mySet:
                    temp = two
                    two = one + two
                    one = temp
                    count += 1
                maxCount = max(maxCount, count)
                
        return maxCount + 2 if maxCount else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        max_length = 0
        S = set(A)
        
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                x, y = A[i], A[j]
                expected = x+y
                length = 2
                while expected in S:
                    x=y
                    y=expected
                    expected = x+y
                    length += 1
                
                max_length = max(max_length, length)
                    
        return max_length if max_length >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        res = 2
        for i in range(len(A)):
            for j in range(i + 1,len(A)):
                a = A[i]
                b = A[j]
                l = 2
                
                while a + b in s:
                    a,b,l = b,a + b,l + 1
                res = max(res,l) % (10 ** 9 + 7)
        return res if res > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        res = 0
        A_dict = {}
        for x in A:
            A_dict[x] = A_dict.get(x,0) + 1
        
        for i in range(len(A)-1):
            for j in range(i+1, len(A)):
                a, b = A[i], A[j] # loop all initial candidates
                c = a + b
                length = 0
                while c in A_dict:
                    length += 1
                    a, b = b, c
                    c = a + b
                res = max(res, length)
                
        return res + 2 if res > 0 else 0
                
                


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        def getLength(orgprev,orgcurr,prev,curr):
            nxt = curr+prev
            if nxt in Aset:
                return 1+getLength(orgprev,orgcurr,curr,nxt)
            else:
                return 2 if orgprev != prev and orgcurr != curr else 0
        Aset = set(A)
        return max(max([getLength(a,b,a,b) for a in A[:i]],default=float('-inf')) for i,b in enumerate(A))


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        dp = defaultdict(int)
        ans = 0
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                prev, curr, l = A[i], A[j], 0
                while prev + curr in s:
                    l += 1
                    dp[prev+curr] = l
                    prev, curr = curr, prev + curr
                ans = max(ans, l)
        
        return ans + 2 if ans > 0 else 0

class Solution:
    def lenLongestFibSubseq(self, A):
        s = set(A)
        res = 2
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                a, b, l = A[i], A[j], 2
                while a + b in s:
                    a, b, l = b, a + b, l + 1
                res = max(res, l)
        return res if res > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {x:i for i, x in enumerate(A)}
        longest = collections.defaultdict(lambda: 2)
        result = 0
        
        for k, z in enumerate(A):
            for j in range(k):
                i = index.get(z-A[j], float('inf'))
                if i < j:
                    longest[j, k] = longest[i, j] + 1
                    if longest[j, k] > result:
                        result = longest[j, k]
        
        return result if result >= 3 else 0

class Solution(object):
    def lenLongestFibSubseq(self, A):
        S = set(A)
        ans = 0
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                x, y = A[j], A[i] + A[j]
                length = 2
                while y in S:
                    x, y = y, x + y
                    length += 1
                ans = max(ans, length)
        return ans if ans >= 3 else 0
    



class Solution:
    def new_lenLongestFibSubseq(self, A: List[int]) -> int:
        exists = set(A)                
        max_length = 2
        
        for i in range(len(A)):
            first = A[i]
            for j in range(i):
                second = A[j]
                
                start = second
                curr_length = 2
                
                while (first + second) in exists:
                    curr_length += 1
                    curr = first + second
                    second = first
                    first = curr
                max_length = max(max_length, curr_length)                    

        if max_length < 3: return 0
        return max_length
        
    
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        exists = set(A)        
        max_length = 2
        
        for i in range(len(A)):
            for j in range(i):
                b = A[i]                
                a = A[j]
                curr_length = 2
                
                while (a + b) in exists:
                    curr_length += 1
                    curr = a + b
                    a = b
                    b = curr
                max_length = max(max_length, curr_length)
        
        if max_length <= 2: return 0
        return max_length
    
    
    
    
    
    
    
    
    
    
# [1,2,3,4,5,6,7,8]
# 
# **** START == 1 **** 
#
# second = 1
# first = 2
# curr_length = 3
# curr = 3

# cache[1] = max(cache[1]+1, 3)
# cache[1] = max(0+1, 3)
# cache[1] = 3
# 
# second = 2
# first = 3
# curr_length = 4
# curr = 5
#
# cache[1] = max(cache[1], curr_length)
# cache[1] = max(3, 3)
# cache[1] = 4
#
# second = 3
# first = 5
# curr_length = 5
# curr = 8
# 
# cache[1] = max(cache[1], 5)
# cache[1] = 5
#
# second = 5
# first = 8
# curr_length = 6
# curr = 13
# 
# 13 not in A, next pair
#
#
# **** START == 1 **** 
#
# second = 1
# first = 3
# curr_length = 3
# curr = 4
# 
# cache[1] = max(5, 3)
# cache[1] = 5
#
# second = 3
# first = 4
# curr = 7
# curr_length = 4
# 
# cache[1] = max(5, 4)
# cache[1] = 5
#
# second = 4
# first = 7
# curr = 11
# 
# 11 not in A, exit
#

 
                
        
        
        
        
        
        
        
        
        
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        res=0
        d={x:i for i,x in enumerate(A)}
        n=len(A)
        dp=[[2 for j in range(n)] for i in range(n)]
        for i in range(2,n):
            for j in range(i):
                z=A[i]
                x=A[j]
                y=z-x
                k=d.get(y,-1)
                #x<y<z
                if x<y and k!=-1:
                    dp[i][k]=1+dp[k][j]
                    res=max(res,dp[i][k])
        if res>2:
            return res
        return 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        S = set(A)
        ans = 0
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                x, y = A[j], A[i] + A[j]
                length = 2
                while y in S:
                    x, y = y, x + y
                    length += 1
                ans = max(ans, length)
        return ans if ans >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        if len(A) < 3:
            return 0
        
        S = set(A)
        ans = 0
        for i in range(len(A) - 1):
            for j in range(i + 1, len(A)):
                l = 2
                x, y = A[j], A[i] + A[j]
                while y in S:
                    l += 1
                    x, y = y, x + y
                ans = max(ans, l)
                
        return ans if ans >= 3 else 0


        
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        exists = set(A)        
        max_length = 2
        
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                a = A[i]                
                b = A[j]
                curr_length = 2
                
                while (a + b) in exists:
                    curr_length += 1
                    #curr = a + b
                    #a = b
                    #b = curr
                    a, b = b, a + b
                max_length = max(max_length, curr_length)
        
        if max_length <= 2: return 0
        return max_length
    
    
    
    
    
    
    
    
    
    
# [1,2,3,4,5,6,7,8]
# 
# **** START == 1 **** 
#
# second = 1
# first = 2
# curr_length = 3
# curr = 3

# cache[1] = max(cache[1]+1, 3)
# cache[1] = max(0+1, 3)
# cache[1] = 3
# 
# second = 2
# first = 3
# curr_length = 4
# curr = 5
#
# cache[1] = max(cache[1], curr_length)
# cache[1] = max(3, 3)
# cache[1] = 4
#
# second = 3
# first = 5
# curr_length = 5
# curr = 8
# 
# cache[1] = max(cache[1], 5)
# cache[1] = 5
#
# second = 5
# first = 8
# curr_length = 6
# curr = 13
# 
# 13 not in A, next pair
#
#
# **** START == 1 **** 
#
# second = 1
# first = 3
# curr_length = 3
# curr = 4
# 
# cache[1] = max(5, 3)
# cache[1] = 5
#
# second = 3
# first = 4
# curr = 7
# curr_length = 4
# 
# cache[1] = max(5, 4)
# cache[1] = 5
#
# second = 4
# first = 7
# curr = 11
# 
# 11 not in A, exit
#

 
                
        
        
        
        
        
        
        
        
        
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        S = set(A)
        ans = 0
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                x, y = A[j], A[i] + A[j]
                length = 2
                
                while y in S:
                    x, y = y, x + y
                    length += 1
                    
                ans = max(ans, length)
                
        return ans if ans >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        indexes={A[i]:i for i in range(len(A))}
        dp=[[2 for i in range(len(A))] for j in range(len(A))]
        z=0
        for i in range(1,len(A)):
            for j in range(0,i):
                idx=indexes.get(A[i]+A[j],-1)
                if idx==-1:
                    continue
                else:
                    dp[i][idx]=dp[j][i]+1
            z=max(max(dp[i]),z)
            
        if z<3:
            return 0
        return z
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        set_val = set(A)
        max_len = 0
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                p2, p1 = A[i],A[j]  
                cnt = 0
                while p2 + p1 in set_val:
                    z = p2 + p1
                    p2 = p1
                    p1 = z 
                    cnt += 1
                    
                max_len = max(max_len, cnt + 2 if cnt > 0 else cnt)                        
        return max_len                


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        if len(A) == 0: return A
        result = 0
        aref = set(A)
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                x, y = A[j], A[i] + A[j]
                seq_length = 0
                while y in aref:
                    if seq_length == 0: seq_length = 2
                    seq_length += 1
                    x, y = y, x+y
                result = max(result,seq_length)
        return result
            
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        res = 2
        for i in range(len(A)):
            for j in range(i+1,len(A)):
                a = A[i]
                b = A[j]
                l = 2
                while a + b in s:
                    a,b,l = b,a + b,l + 1
                res = max(res,l) % (10 ** 9 + 7)
        return res if res > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        mapA = {n: i for i, n in enumerate(A)}
        
        # 1. Brutal Force
        l = ans = 0
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                x, y = A[j], A[i] + A[j]
                l = 2
                while y in mapA:
                    x, y = y, x + y
                    l += 1
                ans = max(ans, l)
        return ans if ans >= 3 else 0

from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
#         [1,2,3,4,5,6,7,8]
#         [0,0,3,] 
        memo = defaultdict(int)
        visited = dict()
        visited[A[0]] = True
        visited[A[1]] = True
        ret = 0
        for i in range(2, len(A)):
            num = A[i]
            visited[num] = True
            for j in range(i - 1, -1, -1):
                if num - A[j] in visited and num - A[j] < A[j]:
                    old_key = (num - A[j], A[j])
                    val = memo[old_key] + 1
                    ret = max(ret, val)
                    key = (A[j], num) 
                    # print(old_key)
                    # print(key, val)
                    # print('-----')
                    memo[key] = val
                    
        if ret:
            ret += 2
            
        return ret
                    
                


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        longest = 0
        coll = set(A)
        n = len(A)
        
        lookup = [[None for _ in range(n)] for _ in range(n)] 
        
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                target = A[i] + A[j]
                prev = A[j]
                while target in coll:
                    if lookup[i][j]:
                        lookup[i][j] += 1
                    else:
                        lookup[i][j] = 3
                    temp = target
                    target += prev
                    prev = temp
                    longest = max(longest, lookup[i][j])
                    
        return longest

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        s = set(A)
        n = len(A)
        result = 0
                  
        for i in range(n-1):
            for j in range(i+1, n):
                a, b = A[i], A[j]
                count = 2
                while a+b in s:
                    a, b = b, a+b
                    count += 1
                result = max(result, count)
                    
        return result if result > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        S = set(A)
        n = len(A)
        res = 0
        for i in range(n):
            for j in range(i+1,n):
                x, y = A[j],A[i] + A[j]
                ans = 2
                while y in S:
                    x, y = y, x + y
                    ans += 1
                res = max(res, ans)
        return res if res >= 3 else 0
    
    
    


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        res = 2
        for i in range(len(A)):
            for j in range(i + 1,len(A)):
                a = A[i]
                b = A[j]
                l = 2
                while a + b in s:
                    a,b,l = b,a + b,l + 1
                res = max(res,l) % (10 ** 9 + 7)
        return res if res > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n, s, res = len(A), set(A), 0
        for i in range(n):
            for j in range(i+1, n):
                x, y, l = A[j], A[i] + A[j], 2
                while y in s:
                    x, y = y, x + y
                    l += 1
                res = max(res, l)
        return res if res > 2 else 0
    


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        exists = set(A)                
        max_length = 2
        
        for i in range(len(A)):
            for j in range(i):
                first = A[i]                
                second = A[j]
                
                start = second
                curr_length = 2
                
                while (first + second) in exists:
                    curr_length += 1
                    curr = first + second
                    second = first
                    first = curr
                max_length = max(max_length, curr_length)                    

        if max_length < 3: return 0
        return max_length
        
    
    def old_lenLongestFibSubseq(self, A: List[int]) -> int:
        exists = set(A)        
        max_length = 2
        
        for i in range(len(A)):
            for j in range(i):
                b = A[i]                
                a = A[j]
                curr_length = 2
                
                while (a + b) in exists:
                    curr_length += 1
                    curr = a + b
                    a = b
                    b = curr
                max_length = max(max_length, curr_length)
        
        if max_length <= 2: return 0
        return max_length
    
    
    
    
    
    
    
    
    
    
# [1,2,3,4,5,6,7,8]
# 
# **** START == 1 **** 
#
# second = 1
# first = 2
# curr_length = 3
# curr = 3

# cache[1] = max(cache[1]+1, 3)
# cache[1] = max(0+1, 3)
# cache[1] = 3
# 
# second = 2
# first = 3
# curr_length = 4
# curr = 5
#
# cache[1] = max(cache[1], curr_length)
# cache[1] = max(3, 3)
# cache[1] = 4
#
# second = 3
# first = 5
# curr_length = 5
# curr = 8
# 
# cache[1] = max(cache[1], 5)
# cache[1] = 5
#
# second = 5
# first = 8
# curr_length = 6
# curr = 13
# 
# 13 not in A, next pair
#
#
# **** START == 1 **** 
#
# second = 1
# first = 3
# curr_length = 3
# curr = 4
# 
# cache[1] = max(5, 3)
# cache[1] = 5
#
# second = 3
# first = 4
# curr = 7
# curr_length = 4
# 
# cache[1] = max(5, 4)
# cache[1] = 5
#
# second = 4
# first = 7
# curr = 11
# 
# 11 not in A, exit
#

 
                
        
        
        
        
        
        
        
        
        
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        d1={x:i for i,x in enumerate(A)}
        d2={}
        ans=0
        for i in range(1,len(A)):
            for j in range(i):
                d2[(j,i)]=2
                val= A[i]-A[j]
                if(val in d1 and d1[val]<j):
                    d2[(j,i)]=d2[(d1[val],j)]+1
                    ans=max(ans,d2[(j,i)])
                    
        
        if(ans>=3):
            return ans
        return 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        if n < 3:
            return 0
        # dp = [[2 for j in range(n)] for i in range(n)]
        # ans = 2
        # hmap = {A[0]:0, A[1]:1}
        # for i in range(2, n):
        #     for j in range(1, i):
        #         pos = hmap.get(A[i]-A[j], -1)
        #         if pos >= 0 and pos < j:
        #             dp[i][j] = max(dp[i][j], dp[j][pos]+1)
        #             ans = max(ans, dp[i][j])
        #     hmap[A[i]] = i
        # return ans if ans > 2 else 0
        
        dp = [[2 for j in range(n)] for i in range(n)]
        ans = 2
        for i in range(2, n):
            l, r = 0, i-1
            while l < r:
                if A[l] + A[r] == A[i]:
                    dp[i][r] = max(dp[i][r], dp[r][l] + 1)
                    ans = max(ans, dp[i][r])
                    l += 1
                    r -= 1
                elif A[l] + A[r] < A[i]:
                    l += 1
                else:
                    r -= 1 
        return ans if ans > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        def _helper(l1, l2, cache):
            if A[l1] + A[l2] in table:
                l1, l2 = l2, table[A[l1] + A[l2]]
                return _helper(l1, l2, cache + 1)
            else:
                return cache if cache >= 3 else 0
        ans = 0
        table = {v:i for i, v in enumerate(A)}
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                if A[i] + A[j] > A[-1]: break
                ans = max(ans, _helper(i, j, 2))
        return ans
            


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        # dp = [[0 for i in range(len(A))] for j in range(len(len(A)))]
        ans = 0
        d={}
        for i in range(len(A)):
            d[A[i]] = 1
        
        for i in range(len(A)):
            for j in range(i+1,len(A)):
                a = A[i]
                b = A[j]
                l=2
                while(d.get(a+b)!=None):
                    l+=1
                    temp = b
                    b = a+b
                    a = temp
                    
                ans = max(l,ans)
        
        if(ans>2):
            return ans
        return 0
                


class Solution:
    def lenLongestFibSubseq(self, nums: List[int]) -> int:
        n=len(nums)
        dp=[[0 for x in range(n)] for y in range(n)]
        max_=0
        for i in range(2,n):
            l=0
            r=i-1
            
            while l<=r:
                s=nums[l]+nums[r]
                if s>nums[i]:
                    r-=1
                elif s<nums[i]:
                    l+=1
                else:
                    dp[r][i]=dp[l][r]+1
                    max_=max(max_,dp[r][i])
                    l+=1
                    r-=1
        return max_ if max_==0 else max_+2
                    


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        s = set()
        for i in A:
            s.add(i)
        res = 0
        ll = 0
        for i in range(n):
            for j in range(i+1,n):
                f1 = A[i]
                f2 = A[j]
                if f1+f2 in s:
                    ll = 2
                while f1+f2 in s:
                    ll += 1
                    tmp = f2
                    f2 = f1+f2
                    f1 = tmp
                res = max(res,ll)
        return res
                    
                


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        from collections import defaultdict
        used_tuples = set()
        max_len = 0
        hist = set(A)
        for i in range(len(A) - 1):
            for j in range(i + 1, len(A)):
                curr_len = 0
                s = A[i]
                l = A[j]
                if (s,l) in used_tuples: 
                    continue
                while s+l in hist:
                    curr_len += 1
                    used_tuples.add((s,l))
                    old_s = s
                    s = l
                    l = s + old_s
                    
                max_len = max(max_len, curr_len)
        
        return max_len + 2 if max_len > 0 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        
        dp = collections.defaultdict(int)
        
        ret = 0
        
        a_set = set(A)
        
        for i in range(n):
            for j in range(i + 1, n):
                dp[(A[i], A[j])] = 2
                
                left = A[j] - A[i]
                
                if left > A[i] or left not in a_set:
                    continue
                
                dp[(A[i], A[j])] = max(dp[(A[i], A[j])], dp[(left, A[i])] + 1)
                
                ret = max(ret, dp[(A[i], A[j])]) 
        
        return ret

class Solution:
    def lenLongestFibSubseq(self, a: List[int]) -> int:
        s=set(a)
        c=0
        for i in range(len(a)):
            for j in range(i+1,len(a)):
                x,y,l=a[i],a[j],2
                while x+y in s:
                    x,y=y,x+y
                    l+=1
                c=max(c,l)
        return c if c>2 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        max_l = 0
        cache = [[0 for j in range(n)] for i in range(n)]
        a_dict = {number: index for (index, number) in enumerate(A)}
        
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, i, -1):
                if j == n - 1:
                    cache[i][j] = 2
                else:
                    target = A[i] + A[j]
                    if target in a_dict:
                        cache[i][j] = cache[j][a_dict[target]] + 1

                    else:
                        cache[i][j] = 2
                if cache[i][j] > 2:
                    max_l = max(cache[i][j], max_l)   
        return max_l

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        pos = {A[i]: i for i in range(len(A))}
        dp = [[2 for j in range(len(A))] for i in range(len(A))]

        maxlen = 0
        for z in range(2, len(A)):
            for x in range(z):
                y = pos.get(A[z] - A[x], -1)
                if A[x] < (A[z] - A[x]) and y != -1:
                    dp[z][y] = dp[y][x] + 1
                    maxlen = max(maxlen, dp[z][y])

        return maxlen if maxlen > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        N=len(A)
        index={n:i for i,n in enumerate(A)}
        dp=collections.defaultdict(lambda: 2)
        res=0
        
        for i2 in range(N):
            for i1 in range(i2-1,-1,-1):
                n0=A[i2]-A[i1]
                if n0>=A[i1]:
                    break
                
                if n0 in index:
                    i0=index[n0]
                    dp[(i1,i2)]=dp[(i0,i1)]+1
                    res=max(res,dp[(i1,i2)])
        
        return res


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        
        dp = collections.defaultdict(int)
        
        ret = 0
        
        a_set = set(A)
        
        for i in range(n):
            for j in range(i + 1, n):
                dp[(A[i], A[j])] = 2
                
                left = A[j] - A[i]
                
                if left >= A[i] or left not in a_set:
                    continue
                
                #print(left, A[i], A[j], dp[(left, A[i])])
                
                dp[(A[i], A[j])] = dp[(left, A[i])] + 1
                
                ret = max(ret, dp[(A[i], A[j])]) 
        
        return ret

class Solution:
    #from collections import deafal
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        s = set(A)
        
        def helper(i,j):
            ans = 2
            while(True):
                k = i+j
                if(k in s and k<=10**9):
                    ans +=1
                    i = j
                    j = k
                else:
                    break
            return ans
        
        
        c = 0
        for i in reversed(list(range(n-2))):
            for j in reversed(list(range(i+1,n-1))):
                c = max(c,helper(A[i],A[j]))
        return c if c>2 else 0
                


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        longest = 0
        coll = set(A)
        n = len(A)
        
        lookup = [[0 for _ in range(n)] for _ in range(n)] 
        
        j = 1
        for i in range(n - 2):
            if n - i + 2 < longest - lookup[i][j]:
                break
            for j in range(i + 1, n - 1):
                if n - j + 1 < longest - lookup[i][j]:
                    break
                target = A[i] + A[j]
                prev = A[j]
                while target in coll:
                    if lookup[i][j]:
                        lookup[i][j] += 1
                    else:
                        lookup[i][j] = 3
                    temp = target
                    target += prev
                    prev = temp
                    longest = max(longest, lookup[i][j])
                    
        return longest

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        d = {}
        for i, v in enumerate(A):
            d[v] = i
            
        l = len(A)
        
        res = -1
        for i in range(0, l):
            
            for j in range(i+1, l):
            
                one_behind = A[j]
                two_behind = A[i]
                total = one_behind + two_behind


                c = 0
                while total in d:
                    print((total, one_behind, two_behind))
                    if c == 0:
                        c += 3
                    else:
                        c += 1
                    tmp = one_behind
                    one_behind = total
                    two_behind = tmp
                    total = one_behind + two_behind


                res = max(res, c)
            #break
            
        #print(res)
        return res
                
            
                
            

        
        
        
        
        


class Solution:
    def lenLongestFibSubseq(self, nums: List[int]) -> int:
        n, ans = len(nums), 0
        idx = {n: i for i, n in enumerate(nums)}
        dp = [[0]*n for _ in range(n)]
        for j in range(n):
            dp[0][j] = 2
            dp[j][j] = 1
        for i in range(1, n):
            for j in range(i+1, n):
                dp[i][j] = 2
                if nums[i] > nums[j]//2 and nums[j]-nums[i] in idx:
                    ii = idx[nums[j]-nums[i]]
                    dp[i][j] = dp[ii][i] + 1
                ans = max(ans, dp[i][j])
        return ans if ans>2 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        ans = 0
        for i in range(len(A)):
            for j in range(i+1,len(A)):
                x,y = A[j],A[i]+A[j]
                l = 2
                while y in s:
                    x,y = y,x+y
                    l += 1
                ans = max(ans,l)
        return ans if ans >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        d={}
        for i in range(len(A)):
            d[A[i]]=i
        dp=[[2 for i in range(len(A))] for j in range(len(A))]
        ans=0
        for j in range(0,len(A)):
            for i in range(0,j):
                
                if A[j]-A[i] in d and d[A[j]-A[i]]<i:
                    k= d[A[j]-A[i]]
                    dp[i][j]=dp[k][i]+1
                ans=max(dp[i][j],ans)
                
        return ans if ans>=3 else 0
                    
                


class Solution:
    def lenLongestFibSubseq(self, nums: List[int]) -> int:
        n = len(nums)
        idx = {n: i for i, n in enumerate(nums)}
        dp = [[0]*n for _ in range(n)]
        for j in range(n):
            dp[0][j] = 2
            dp[j][j] = 1
        ans = 0
        for i in range(1, n):
            for j in range(i+1, n):
                if nums[i] <= nums[j]//2:
                    dp[i][j] = 2
                else:
                    prev = nums[j]-nums[i]
                    if prev in idx:
                        dp[i][j] = dp[idx[prev]][i] + 1
                    else:
                        dp[i][j] = 2
                ans = max(ans, dp[i][j])
        return ans if ans>2 else 0


from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index_map = { x:i for i, x in enumerate(A) }
        longest = defaultdict(lambda: 2)
        ans = 0
        
        for k in range(len(A)):
            for j in range(len(A)):
                target = A[k] - A[j]
                i = index_map.get(target, -1)
                
                if i >= 0 and i < j:
                    cand = longest[j,k] = longest[i,j] + 1
                    ans = max(ans, cand)
        
        return ans
         


class Solution(object):
    def lenLongestFibSubseq(self, A):
        S = set(A)
        ans = 0
        for i in range(len(A)):
            for j in range(i+1, len(A)):

                x, y = A[j], A[i] + A[j]
                length = 2
                while y in S:
                    x, y = y, x + y
                    length += 1
                ans = max(ans, length)
        return ans if ans >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        res = 2
        S = set(A)  
        for i in range (len(A)-2):
            if A[i] * (res - 1) * (res - 2) > A[-1]:
                break
        
            for j in range (i+1, len(A)-1):
                cnt = 2
                a, b=A[j], A[i]+A[j]
                while b in S:
                    cnt+=1
                    a, b = b, a+b
                res = max(cnt, res)
        if res > 2:
            return res
        else:
            return 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        maxlen = 0
        dp = [[0 for _ in range(len(A))] for _ in range(len(A))]
        for i in range(2, len(A)):
            
            l, r = 0, i - 1
            
            while l < r:
                
                s = A[l] + A[r]
                
                if s > A[i]:
                    r -= 1
                elif s < A[i]:
                    l += 1
                
                else:
                    
                    dp[r][i] = max(dp[r][i], dp[l][r] + 1)
                    maxlen = max(maxlen, dp[r][i])
                    l += 1
                    r -= 1
        
        return maxlen if maxlen == 0 else maxlen + 2
                    


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        length = len(A)
        s = set(A)
        result = 0
        for i in range(length-1):
            
            for j in range(i+1, length):
                a=A[i]
                b=A[j]
                count = 2
                while a+b in s:
                    a,b = b,a+b
                    count+=1
                result = max(result, count)

        return result if result > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        n = len(A)
        count = 0
        for i in range(n):
            for j in range(i+1, n):
                x, y = A[j], A[i]+A[j]
                length = 2
                while y in s:
                    x, y = y, x+y
                    length +=1
                count = max(count, length)                
        return count if count >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        dp = [[2]*n for i in range(n)]

        map_ = collections.defaultdict(int)
        for i,j in enumerate(A):
            map_[j] = i

        # i:end  j:start

        for i in range(2, n):
            for j in range(1, i):
                diff = A[i] - A[j]
                
                if diff in list(map_.keys()) and map_[diff] < j:
                    k = map_[diff]
                    dp[j][i] = max(dp[j][i], dp[k][j] + 1)

        max_ = max(dp[j][i] for i in range(n) for j in range(n))

        if max_ == 2:
            return 0
        else:
            return max_



class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        start = 0
        longest = 0
        cur_total = 0
        root = A[0]
        
        coll = set(A)
        
        n = len(A)
        cur = 2
        target = [[None for _ in range(n)] for _ in range(n)] 
        lookup = [[None for _ in range(n)] for _ in range(n)] 
        
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                target[i][j] = A[i] + A[j]
                prev = A[j]
                while target[i][j] in coll:
                    if lookup[i][j]:
                        lookup[i][j] += 1
                    else:
                        lookup[i][j] = 3
                    temp = target[i][j]
                    target[i][j] += prev
                    prev = temp
                    longest = max(longest, lookup[i][j])
                    
        
        return longest

class Solution:

    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s=set(A)
        maxi=2
        
        for i in range(len(A)-2):
            
            for j in range(i+1, len(A)-1):
                c=2
                a=A[j]
                b=A[i]+A[j]
                while(b in s):
                    c+=1
                    a,b= b, a+b
                maxi=max(maxi, c)
                    
        return maxi if maxi>2 else 0
            
            
                        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        mp = {}
        
        for v in A:
            mp[v] = set()
        
        result = 0
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                a = A[i]
                b = A[j]
                l = 2
                while True:
                    if b in mp[a]:
                        break
                    if l != 2:
                        mp[a].add(b) 
                    c = a + b
                    if c not in mp:
                        break
                    a = b
                    b = c
                    l += 1
                if l < 3:
                    l = 0
                result = max(result, l)
        return result


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        setA=set(A)
        #overlapping=set()
        r=0
        for i in range(len(A)):
            start=A[i]
            for j in range(i+1,len(A)-1):
                prev_prev=start
                prev=A[j]
                count=0
                while prev+prev_prev in setA:
                    #overlapping.add(prev)
                    #overlapping.add(prev_prev)
                    prev_prev,prev=prev,prev+prev_prev
                    count+=1
                r=max(r,count)
        if r!=0:
            return r+2
        else:
            return r

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        d = {}
        for i, v in enumerate(A):
            d[v] = i
            
        l = len(A)
        
        res = -1
        for i in range(0, l):
            for j in range(i+1, l):
            
                one_behind = A[j]
                two_behind = A[i]
                total = one_behind + two_behind


                c = 0
                while total in d:
                    #print(total, one_behind, two_behind)
                    if c == 0:
                        c += 3
                    else:
                        c += 1
                    one_behind, two_behind = total, one_behind
                    total = one_behind + two_behind


                res = max(res, c)
            #break
            
        #print(res)
        return res
                
            
                
            

        
        
        
        
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        indices = {n: i for i, n in enumerate(A)}
        d = defaultdict(lambda: 2)
        ans = 0
        for k, n in enumerate(A):
            for j in range(k-1, 0, -1):
                if (m := n - A[j]) not in indices:
                    continue
                if (i := indices[m]) >= j:
                    break
                d[j, k] = d[i, j] + 1
                ans = max(ans, d[j, k])
        return ans

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        ans = 0
        for i in range(len(A)):
            for j in range(i+1,len(A)):
                x,y = A[i],A[j]
                l = 2
                while x+y in s:
                    x,y = y,x+y
                    l += 1
                ans = max(ans,l)
        return ans if ans >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        d = {}
        for i, v in enumerate(A):
            d[v] = i
            
        l = len(A)
        
        res = -1
        for i in range(0, l):
            
            for j in range(i+1, l):
            
                one_behind = A[j]
                two_behind = A[i]
                total = one_behind + two_behind


                c = 0
                while total in d:
                    #print(total, one_behind, two_behind)
                    if c == 0:
                        c += 3
                    else:
                        c += 1
                    tmp = one_behind
                    one_behind = total
                    two_behind = tmp
                    total = one_behind + two_behind


                res = max(res, c)
            #break
            
        #print(res)
        return res
                
            
                
            

        
        
        
        
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        N = len(A)
        st = set(A)
        res = 2
        for i in range(N):
            for j in range(i+1, N):
                a, b, l = A[i], A[j], 2
                while a + b in st:
                    a, b, l = b, a+b, l+1
                res = max(res, l)
        return res if res > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        two_sum = {}       
        result = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                curr_pair = (A[i], A[j])
                prev_pair = (A[j] - A[i], A[i])
                two_sum[curr_pair] = 2
                if prev_pair in two_sum:
                    two_sum[curr_pair] = max(two_sum[curr_pair], two_sum[prev_pair] + 1)
                    result = max(result, two_sum[curr_pair])
        return result

from collections import Counter
class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        res=0
        d={x:i for i,x in enumerate(A)}
        n=len(A)
        dp=[[2 for j in range(n)] for i in range(n)]
        for i in range(2,n):
            for j in range(i):
                z=A[i]
                x=A[j]
                y=z-x
                k=d.get(y,-1)
                #x<y<z
                if x<y and k!=-1:
                    dp[i][k]=1+dp[k][j]
                    res=max(res,dp[i][k])
        if res>2:
            return res
        return 0

from bisect import bisect_left 
  
def BinarySearch(a, x): 
    i = bisect_left(a, x) 
    if i != len(a) and a[i] == x: 
        return i 
    else: 
        return 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        def get_length(x,y):
            s=0
            while x+y in A:
                s+=1
                x,y = y, x+y
            return s
        if len(A) < 3:
            return 0
        ans = 0
        sum_lim = A[-1]
        for fi in range(len(A)-2):
            curr_ans = 0
            temp_fi = fi
            si = temp_fi+1
            # print(\"======={}====================\".format(fi))
            while si< len(A):
                reqd_sum = A[temp_fi]+A[si]
                if reqd_sum > sum_lim:
                    break
                pres = BinarySearch(A, reqd_sum)
                if pres:
                    # temp_fi = si
                    # si = pres
                    curr_ans = 1+ get_length(A[si], A[pres])
                    ans = max(ans, curr_ans)
                si += 1
        return ans+2 if ans > 0 else ans


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s, memo = set(A), {}
        for i in range(len(A)):
            for j in range(i):
                if (A[i] - A[j]) in s and (A[i] - A[j]) < A[j]:
                    memo[A[j], A[i]] = memo.get( (A[i] - A[j], A[j]), 2) + 1
        return max(memo.values() or [0])

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        # only need the first 2 elements to define a fib seq
        setA = set(A)
        rint = 0
        def getLen(i, j):
            a, b = A[i], A[j]
            if a + b not in setA:
                return 0
            length = 2
            while a + b in setA:
                length += 1
                a, b = b, a + b
            return length
        for i in range(len(A) - 2):
            for j in range(i + 1, len(A) - 1):
                if A[j] - A[i] in setA and A[j] - A[i] < A[i]:
                    continue
                rint = max(rint, getLen(i, j))
                # print(i, j, getLen(i, j))
        return rint

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        longest = 0
        coll = set(A)
        n = len(A)
        
        lookup = [[0 for _ in range(n)] for _ in range(n)] 
        
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                if n - j + 1 < longest - lookup[i][j]:
                    break
                target = A[i] + A[j]
                prev = A[j]
                while target in coll:
                    if lookup[i][j]:
                        lookup[i][j] += 1
                    else:
                        lookup[i][j] = 3
                    temp = target
                    target += prev
                    prev = temp
                    longest = max(longest, lookup[i][j])
                    
        return longest

class Solution:
    def lenLongestFibSubseq(self, nums: List[int]) -> int:
        n=len(nums)
        dp=[[0 for x in range(n)] for y in range(n)]
        max_=0
        for i in range(2,n):
            l=0
            r=i-1
            min_possible=nums[0]+nums[1]
            max_possible=nums[r]+nums[r-1]
            if nums[i]<min_possible or nums[i]>max_possible:
                continue
            while l<=r:
                s=nums[l]+nums[r]
                if s>nums[i]:
                    r-=1
                elif s<nums[i]:
                    l+=1
                else:
                    dp[r][i]=dp[l][r]+1
                    max_=max(max_,dp[r][i])
                    l+=1
                    r-=1
        return max_ if max_==0 else max_+2
                    


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        if len(A) <= 2: return 0
        dp = {(A[1], A[0]): 2}
        maxx = 0
        for i in range(2, len(A)):
            j = i-1
            while j >= 0:
                v = A[i] - A[j]
                if v < A[j] and (A[j], v) in dp:
                    maxx = max(maxx, dp[(A[j], v)]+1)
                    dp[(A[i], A[j])] = dp[(A[j], v)]+1
                else:
                    dp[(A[i], A[j])] = 2
                j -= 1
            #print(dp)
        return maxx
                    
                
            
        


from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, ordered_nums: List[int]) -> int:
        def dfs(prev, curr):
            if (prev, curr) in explored:
                return -1
            elif prev + curr not in unordered_nums:
                return 2
            else:
                explored.add((prev, curr))
                return 1 + dfs(curr, prev + curr)
        
        unordered_nums = {n for n in ordered_nums}
        explored = set()
        path_len = 0
        for i in range(len(unordered_nums)):
            for j in range(i + 1, len(unordered_nums)):
                path_len = max(path_len, dfs(ordered_nums[i], ordered_nums[j]))
        
        return path_len if path_len >= 3 else 0
            
            


from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, nums: List[int]) -> int:
        num_to_idx = {n: i for i, n in enumerate(nums)}
        mat = [[0 for _ in range(len(nums))] for _ in range(len(nums))]
        
        path_len = 0
        for i in range(len(mat)):
            for j in range(i + 1, len(mat)):
                n = nums[j] - nums[i]
                if n < nums[i] and n in num_to_idx:
                    mat[i][j] = mat[num_to_idx[n]][i] + 1
                else:
                    mat[i][j] = 2
                    
                path_len = max(path_len, mat[i][j])
                
        return path_len if path_len >= 3 else 0
                
            
            


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        S = set(A)
        res = 0
        for i in range(len(A)):
            for j in range(i+1,len(A)):
                f1 ,f2= A[i],A[j]
                length = 0
                if(f1+f2 in S):
                    length = 2
                while(f1+f2 in S):
                    length+=1
                    tmp = f1+f2
                    f1 = f2
                    f2 = tmp
                res = max(length,res)
        return res

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        S = set(A)
        
        ans = 2
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                a = A[i]
                b = A[j]
                l = 2
                while((a+b) in S):
                    temp = a
                    a = b
                    b = temp + b
                    l += 1
                
                ans = max(ans, l)
        
        if ans < 3:
            return 0
        return ans
                    


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        S = set(A)
        res = 2
        for i in range(len(A) - 2):
            if A[i] * (res - 1) * (res - 2) > A[-1]:
                break
            for j in range(i + 1, len(A) - 1):
                cnt = 2
                a, b = A[j], A[i] + A[j]
                while b in S:
                    cnt += 1
                    a, b = b, a + b
                res = max(res, cnt)
        return res if res > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        A.sort()
        S = (set(A))
        maxlen = 0
        
        for i in range(len(A)):
            for j in range(i+1,len(A)):
                    a,b = A[j],A[i]+A[j]
                    count = 2
                    while b in S:
                        count+=1
                        a,b = b,a+b
                    maxlen = max(maxlen,count)
        if maxlen >= 3:
            return maxlen
        return 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        dp = dict()
        for i in A:
            dp[(i,i)] = 0
        
        n = len(A)
        
        for i in range(n):
            for j in range(i+1,n):
                
                if A[j]-A[i]<A[i] and A[j]-A[i]>=0 and (A[j]-A[i],A[i]) in dp: 
                    val = dp[(A[j]-A[i],A[i])] + 1
                else:
                    val = 2
                dp[(A[i],A[j])] = val
        a = max(list(dp.values()))
        if a>2:
            return a
        return 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        
        longest = 0
        coll = set(A)
        n = len(A)
        
        target = [[None for _ in range(n)] for _ in range(n)] 
        lookup = [[None for _ in range(n)] for _ in range(n)] 
        
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                target[i][j] = A[i] + A[j]
                prev = A[j]
                while target[i][j] in coll:
                    if lookup[i][j]:
                        lookup[i][j] += 1
                    else:
                        lookup[i][j] = 3
                    temp = target[i][j]
                    target[i][j] += prev
                    prev = temp
                    longest = max(longest, lookup[i][j])
                    
        return longest

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        mp = {}
        
        for v in A:
            mp[v] = set()
        
        result = 0
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                a = A[i]
                b = A[j]
                l = 2
                while True:
                    if b in mp[a]:
                        break
                    mp[a].add(b) 
                    c = a + b
                    if c not in mp:
                        break
                    a = b
                    b = c
                    l += 1
                if l < 3:
                    l = 0
                result = max(result, l)
        return result


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        unique = set(A)

        max_len = 0
        for i in range(len(A) - 2):
            for j in range(i + 1, len(A) - 1):
                f, s = A[i], A[j]
                length = 2
                while f + s in unique:
                    f, s = s, f + s
                    length += 1
                max_len = max(max_len, length)

        return 0 if max_len == 2 else max_len


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        # dp = {prev_val, next_val: len}
        dp = {}
        dp[(A[1], A[0] + A[1])] = 2
        for i in range(2, len(A)):
            for j in range(i):
                if (A[j], A[i]) not in dp:
                    dp[(A[i], A[j] + A[i])] = 2
                else:
                    dp[(A[i], A[j] + A[i])] = dp[(A[j], A[i])] + 1
                    del dp[(A[j], A[i])]
                #print(A[i], A[j], dp)
        longest = max(dp.values())
        
        return longest if longest > 2 else 0
        
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        setA=set(A)
        r=0
        for i in range(len(A)):
            start=A[i]
            for j in range(i+1,len(A)):
                prev_prev=start
                prev=A[j]
                count=0
                while prev+prev_prev in setA:
                    prev_prev,prev=prev,prev+prev_prev
                    count+=1
                r=max(r,count)
        if r!=0:
            return r+2
        else:
            return r

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        S = set(A)
        res = 2
        for i in range(len(A)-2): 
            if A[i] * (res - 1) * (res - 2) > A[-1]:
                break
            for j in range(i + 1, len(A) - 1):
                cnt = 2
                a, b = A[j], A[i] + A[j]
                while b in S: 
                    cnt += 1
                    a, b = b , a + b
                res = max(res, cnt) 
        return res if res > 2 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        L=len(A)
        if L<=2:
            return 0
        
        res=dict()
        for j in range(1,L):
            res[A[0],A[j]]=2
            for i in range(1,j):
                if (A[j]-A[i], A[i]) in res:
                    res[A[i],A[j]]=max(res.get((A[i],A[j]), 2), res[A[j]-A[i],A[i]]+1)
                else:
                    res[A[i],A[j]]=2
        maxx=max(list(res.values()))
        if maxx>=3:
            return maxx
        else:
            return 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        longest = 2
        # brute force type of way
        # start with each pair and build the highest fib sequence you can
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                x, y = A[i],A[j] 
                seqlen = 2
                while x+y in s:
                    x, y = y, x + y
                    seqlen += 1
                longest = max(seqlen, longest)
                
                
        return longest if longest > 2 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        two_sum = {}
        for i in range(n - 1):
            for j in range(i + 1, n):
                two_sum[(A[i], A[j])] = 2
        
        result = 0
        for i in range(n - 1):
            for j in range(i + 1, n):
                if (A[j] - A[i], A[i]) in two_sum:
                    two_sum[(A[i], A[j])] = max(two_sum[(A[i], A[j])], two_sum[(A[j] - A[i], A[i])] + 1)
                    result = max(result, two_sum[(A[i], A[j])])
        return result

from functools import lru_cache

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        S = set(A)
        
        @lru_cache(None)
        def fib(p1, p2):
            prevsum = p1 + p2
            if prevsum in S:
                return 1 + fib(p2, prevsum)
            return 0
                
        
        res = 0
        for i in range(n-2):
            for j in range(i+1, n-1):
                curres = fib(A[i], A[j])
                if curres:
                    res = max(res, 2+curres)
        return res

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        # Create a hashmap to find index from value
        val_to_idx = {val: idx for idx, val in enumerate(A)}

        def maxLevel(A: List[int], sum_idx: int, var2_idx: int, level: int) -> int:
            if var2_idx==0:
                return level
            #print(f\"In maxLevel: sum={A[sum_idx]} (index={sum_idx}), var2={A[var2_idx]} (index={var2_idx}), level={level}\")
            val_to_search = A[sum_idx] - A[var2_idx]
            returned_idx = val_to_idx.get(val_to_search, None)
            if returned_idx is not None and returned_idx<var2_idx:
                #print(f\"Found value at index: {returned_idx}\")
                return maxLevel(A, var2_idx, returned_idx, level + 1)
            #print(f\"Index not found, returning level: {level}\")
            return level


        longest = 0
        for i in reversed(list(range(len(A)))):
            for j in reversed(list(range(i))):
                result_length = maxLevel(A, i, j, 2)
                longest = max(longest, result_length)

        if longest < 3:
            return 0
        return longest


class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        fibSeqs = {}
        ans = 0
        for i3 in range(1, len(arr)):
            for i2 in reversed(range(i3)):
                v1 = arr[i3] - arr[i2]
                cl = fibSeqs.get((v1, arr[i2]))
                if cl is None:
                    fibSeqs[(arr[i2], arr[i3])] = 0
                    continue

                if arr[i2] < v1:
                    break

                fibSeqs[(arr[i2], arr[i3])] = cl+1
                ans = max(ans, cl+3)

        return ans

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int: 
        dp = []
        
        for i, x in enumerate(A):
            nd = collections.defaultdict(lambda: 1)
            dp.append(nd)
            for j in range(i):
                prev = x - A[j]
                dp[i][A[j]] = dp[j][prev] + 1
        temp = [max(y.values()) for y in dp if y!={}]
        if temp:
            result = max(temp)
            return result if result>=3 else 0
        return 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        mem = {}
        
        for idx, x in enumerate(A):
            for i2 in range(idx):
                v2 = A[i2]
                if v2 < x:
                    mem[(v2, x)] = 1 + mem.get((x - v2, v2), 1)
        res = max(mem.values())
        return 0 if res == 2 else res

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        res = 2
        s = set(A)
        for i in range(len(A)):
            for j in range(i+1, len(A)): 
                a, b, l = A[i], A[j], 2
                while (a+b) in s:
                    a,b = b, a+b
                    l += 1 
                
                res = max(res, l)

        print(res)

        if res > 2:
            return res
        else:
            return 0 


            
            
            


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dp = [collections.defaultdict(int) for _ in range(len(A))]
        
        longest_seq = 0
        s = set(A)
        for i in range(2, len(A)):
            for j in range(i):
                if A[i] - A[j] in s and A[i] - A[j] < A[j]:
                    two_ago = A[i] - A[j]
                    one_ago = A[j]
                    if dp[j][two_ago] > 0:
                        dp[i][one_ago] = dp[j][two_ago] + 1
                    else:
                        dp[i][one_ago] = 3
                            
                    longest_seq = max(longest_seq, dp[i][one_ago])
                    
        return longest_seq


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        if len(A)<=2:
            return 0
        N=len(A)
        ans=0
        dp=dict()
        dp[(A[1],A[0])]=2
        for i in range(2,N):
            for j in range(i):
                if (A[j],A[i]-A[j]) in dp:
                    z=dp[(A[j],A[i]-A[j])]
                    ans=max(z+1,ans)
                    dp[(A[i],A[j])]=z+1
                else:
                    dp[(A[i],A[j])]=2
        return ans

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        def getFS(x1, x2):
            F = [x1, x2]
            while F[-1] <= 1000000000:
                F.append(F[-2] + F[-1])
            return F

        C1 = getFS(1, 0)
        C2 = getFS(0, 1)
        
        def getLLFS(start, x1, x2):
            max_len = 2
            F = [x1, x2]
            xi = x1 + x2
            for i in range(start, len(A)):
                if A[i] == xi:
                    max_len += 1
                    F.append(xi)
                    xi = F[-2] + F[-1]
            return max_len
        
        if len(A) < 3:
            return len(A)
        
        max_len = 2
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                x1, x2 = A[i], A[j]
                last = x1 * C1[max_len-1] + x2 * C2[max_len-1]
                
                if last > A[-1]:
                    break
                max_len = max(max_len, getLLFS(j + 1, x1, x2))
        if max_len < 3:
            return 0
        return max_len
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        N = len(A)
        indexes = {x:i for i, x in enumerate(A)}
        longest = defaultdict(lambda: 1)
        for i in range(1, N):
            for j in range(i):
                k = indexes.get(A[i] - A[j], -1)
                longest[(i, j)] = longest[(j, k)] + 1
        # print(longest)
        longest = max(longest.values())
        return longest if longest >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        d = set()
        n = len(A)
        for c in A:
            d.add(c)
            
        max_l = 0
        for i in range(n-2):
            for j in range(i+1, n-1):
                a = A[i]
                b = A[j]
                count = 0
                while (a+b) in d:
                    count += 1
                    a,b = b,a+b
                max_l = max(max_l, count+2)
                
        if max_l >= 3:
            return max_l
        return 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        '''  
        # intuitive, TLE
        dp = {i:[[A[i]]] for i in range(len(A))}
        res = 0
        for i in range(1, len(A)):
            for j in range(i):
                for sequence in dp[j]:
                    if len(sequence) <= 1 or\\
                        sequence[-2]==A[i]-sequence[-1]:
                        dp[i] += [sequence+[A[i]]]
                        if len(dp[i][-1]) >= 3:
                            res = max(res, len(dp[i][-1]))
        return res
        '''
        # kinda of like prefix sum problem
        dp = {}
        for i in range(len(A)):
            b = A[i]
            for j in range(i):
                a = A[j]
                if (b-a, a) not in dp:
                    dp[(a, b)] = 2
                elif b-a < a:
                    dp[(a, b)] = dp[(b-a, a)]+1
        res = max(dp.values())
        #print(dp)
        return res if res!=2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        check = set(A)
        dp = {}
        def helper(i, j):
            if (i, j) in dp:
                return dp[(i, j)]
           
            total = i + j
            if total not in check:
                result = 2
            else:
                val = helper(j, total)
                result = val + 1
            dp[(i, j)] = result
            return result
        for i in range(n):
            for j in range(i+1, n):
                helper(A[i], A[j])
        result = max(dp.values())
        return result if result > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        dp = [[2]*n for i in range(n)]

        map_ = collections.defaultdict(int)
        for i,j in enumerate(A):
            map_[j] = i+10000

        # i:end  j:start

        for i in range(2, n):
            for j in range(1, i):
                diff = A[i] - A[j]

                if map_[diff] > 0 and map_[diff]-10000 < j:
                    k = map_[diff]-10000
                    dp[j][i] = max(dp[j][i], dp[k][j] + 1)

        max_ = max(dp[j][i] for i in range(n) for j in range(n))

        if max_ == 2:
            return 0
        else:
            return max_



from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, nums: List[int]) -> int:
        num_to_idx = {n: i for i, n in enumerate(nums)}
        mat = {}
        
        path_len = 0
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                n = nums[j] - nums[i]
                if n < nums[i] and n in num_to_idx:
                    mat[(i, j)] = mat[(num_to_idx[n], i)] + 1
                else:
                    mat[(i, j)] = 2
                    
                path_len = max(path_len, mat[(i, j)])
                
        return path_len if path_len >= 3 else 0
                
            
            


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dp={}
        dp[(A[0], A[1])]=2
        curmax=2
        
        for i in range(2, len(A)):
            for j in range(i):
                prev=dp[(A[i]-A[j], A[j])] if (A[i]-A[j], A[j]) in dp else 1
                dp[(A[j], A[i])]=1+prev
                curmax=max(curmax, 1+prev)
        if curmax<3:
            return 0
        return curmax

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        st = set(A)
        lenth = 0
        dq = collections.deque()
        
        for j in range(1, len(A) -1):
            for i in range(j):
                if A[i]+A[j] in st:
                    lenth = 3
                    dq.append([3, A[j], A[i] + A[j]])

        while dq:
            sz = len(dq)
            for _ in range(sz):
                s = dq.popleft()
                if s[1] + s[2] in st:
                    s[0], s[1], s[2] = s[0] + 1, s[2], s[1] + s[2]
                    lenth = max(lenth, s[0])
                    dq.append(s)
        return lenth
# class Solution:
#     def lenLongestFibSubseq(self, A: List[int]) -> int:
#         n = len(A)
#         s = set(A)
#         res = 0
#         for i in range(n):
#             for j in range(i + 1, n):
#                 a, b = A[i], A[j]
#                 tep = 2
#                 while a + b in s:
#                     tep += 1
#                     a, b = b, a + b
#                 if tep >= 3: res = max(tep, res)
#                 # if res >= n - j: break
#             # if res >= n - i: return res
#         return res


import bisect

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        dp = [0] * n
        for i in range(0, n):
            dp[i] = [0] * n
        
        record = {elem: idx for idx, elem in enumerate(A)}
        
        for i in range(0, n-1):
            for j in range(i+1, n):
                target = A[j] - A[i]
                if target in record and record[target] < i:
                    k = record[target]
                    dp[i][j] = max(dp[i][j], dp[k][i]+1)
        ans = 0
        for i in range(0, n):
            for j in range(0, n):
                ans = max(ans, dp[i][j])
        
        if ans > 0:
            return ans+2
        return 0

from functools import lru_cache
from itertools import combinations


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        val2idx = {v: i for i, v in enumerate(A)}
        
        @lru_cache(None)
        def longest_fib_with_first_second(first, second):
            third = val2idx.get(A[first] + A[second], None)
            if third:
                return 1 + longest_fib_with_first_second(second, third)
            return 2

        ret = max(
            longest_fib_with_first_second(i, j)
            for i, j in combinations(list(range(len(A))), 2)
        )
        return ret if ret >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        set_a = set(A)        
        seen = set()
        
        n = len(A)
        last = A[-1]
        
        g = 0
        
        def dfs(x, y):
            seen.add((x, y))
            if (z := x + y) in set_a:
                return 1 + dfs(y, z)
            else:
                return 0
              
        for i in range(n - 1):
            for j in range(i + 1, n):
                if A[i] + A[j] > last:
                    break
                if (A[i], A[j]) in seen:
                    continue
                g = max(g, dfs(A[i], A[j]))
                
                
                
                
        return g + 2 if g else 0      

class Solution:
    def lenLongestFibSubseq(self, lst: List[int]) -> int:
        
        
        
        m = 0
        dp ={}
        for i in range(len(lst)):
            for j in range(i):

                j1 = (j,lst[i])
                i1 = (i,lst[i]+lst[j])

                if j1 in dp:
                    dp[i1] = 1 + dp[j1]
                else:
                    dp[i1] = 2
                m = max(m,dp[i1])
        if m <3:
            return 0
        return m

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        result = 0 
        from collections import Counter
        d = Counter(A)
        for i in range(len(A)-1):
            for j in range(i+1,len(A)):
                x,y = A[i],A[j]
                temp = 0
                while d[x+y] != 0:
                    x,y = y,x+y
                    temp += 1
                result = max(result,temp)
        print(result+2)
        return (result+2 if result > 0 else 0)

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        setA=set(A)
        overlapping=set()
        r=0
        for i in range(len(A)):
            start=A[i]
            for j in range(i+1,len(A)-1):
                prev_prev=start
                prev=A[j]
                count=0
                while prev+prev_prev in setA:
                    overlapping.add(prev)
                    overlapping.add(prev_prev)
                    prev_prev,prev=prev,prev+prev_prev
                    count+=1
                r=max(r,count)
        if r!=0:
            return r+2
        else:
            return r

from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        A_indices = {a: i for i, a in enumerate(A)}
        memo = {}
        self.best = 2
        def get_value(i, j):
            if (i, j) in memo:
                return memo[i, j]
            # search for A[i] + A[j] in A
            if A[i] + A[j] in A_indices:
                memo[i, j] = 1 + get_value(j, A_indices[A[i] + A[j]])
                self.best = max(self.best, memo[i, j])
            else:
                memo[i, j] = 2
            return memo[i, j]
                    
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                get_value(i, j)

        return self.best if self.best > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        A_set = set(A)
        res_set = []
        res = 0
        for i in range(n-2):
            for j in range(i+1,n):
                if A[i] + A[j] in A_set:
                    res_set.append((A[j],A[i]+A[j]))
        if res_set:
            res = 3
        else:
            return 0
        
        while res_set:
            length = len(res_set)
            while length:
                x,y = res_set.pop(0)
                if x+y in A_set:
                    res_set.append((y,x+y))
                length -= 1
            if res_set:
                res += 1
        return res


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        if len(A)<3:
            return 0
        dic={}
        m=max(A)
        for i in range(len(A)):
            dic[A[i]]=1
        m=0
        for i in range(len(A)):
            for j in range(i+1,len(A)):
                c=2
                a=A[i]
                b=A[j]
                try:
                    while dic[a+b]==1:
                        temp=b
                        b=a+b
                        a=temp
                        c+=1
                except KeyError:
                    m=max(m,c)
                m=max(m,c)
        if m<3:
            return 0
        return m


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {}
        for i in range(len(A)):
            index[A[i]] = i
        record = {}
        
        def dp(i,j):
            if (i,j) in record:
                return record[(i,j)]
            if A[i] + A[j] in index:
                res = 1 + dp(j, index[A[i]+A[j]])
                record[(i,j)] = res
                return res
            else:
                return 2
        
        res = 0
        for i in range(len(A)-1):
            for j in range(i+1, len(A)):
                res = max(res, dp(i,j))
        if res >= 3:
            return res
        else:
            return 0

class Solution:
    def lenLongestFibSubseq(self, x: List[int]) -> int:
        def func(a,b):
            if (a,b) in dp:
                return dp[a,b]
            ans=1
            if (a+b) in f:
                ans=1+func(b,a+b)
            dp[a,b]=ans
            return ans
        l=len(x)
        f=set(x)
        dp={}
        ma=2
        for i in range(l):
            a=x[i]
            for j in range(i+1,l):
                b=x[j]
                ma=max(1+func(a,b),ma)
        return ma if ma>2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        #DP(x,y) = length, expected number for the next, the last number
        
        #how to update?
        
        #DP(x,y) = max(1 + DP(x,y` <y)), 
        
        #store values in the 
        if(len(A)==0):
            return 0
        mem = {}
        dp = [[-1 for x in range(len(A))] for y in range(len(A))]
        for idx,a in enumerate(A):
            mem[a]=idx
        max_l = 1
        for i in range(len(A)-1):
            for j in range(i+1,len(A)):
                max_l = max(2+self.get_valid_pibo(i,j,dp,A,mem),max_l)
                
        if(max_l==2):max_l=0
        return max_l
    def get_valid_pibo(self,i,j,dp,A,mem):
        if(dp[i][j]==-1):
            #return dp[i][j]
            #else:
            next_val = A[i]+A[j]
            if(next_val in mem):
                length = 1+self.get_valid_pibo(j,mem[next_val],dp,A,mem)                
                dp[i][j]=length
            else:
                length = 0            
                dp[i][j]=0
        return dp[i][j]

        
            


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)  
        set_a = set(A)
        seen = set()
        
        res = 0
        store = {}
        
        def find(x, y):
          if x + y in set_a:  
              return 1 + find(y, x + y)
          else:  
              return 0
          
                
        for i in range(n):        
            for j in range(i + 1, n):
                if (A[i], A[j]) not in seen:
                    res = max(find(A[i], A[j]), res)  
                
        if res == 0:      
            return 0
        else:
            return res + 2



class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        num_set = set(A)
        used = set()
        
        max_len = 2
        for x in range(len(A)):
            a = A[x]
            for y in range(x+1, len(A)):
                i, j = a, A[y]

                if (i, j) not in used:
                    used.add((i, j))
                    count = 2
                    while i+j in num_set:
                        count += 1
                        i, j = j, i+j
                        used.add((i, j))
                        
                    max_len = max(count, max_len)
        return 0 if max_len == 2 else max_len
            


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dp = dict()
        res = 1
        for i in range(len(A)):
            for j in range(i):
                if (A[j], A[i]-A[j]) in dp:
                    dp[(A[i], A[j])] = dp[(A[j], A[i]-A[j])] + 1
                else:
                    dp[(A[i], A[j])] = 2
                
                res = max(res, dp[(A[i], A[j])])
                
        return res if res > 2 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dp = dict()
        res = 2
        for i in range(len(A)):
            for j in range(i):
                if (A[j], A[i]-A[j]) in dp:
                    dp[A[i], A[j]] = dp[A[j], A[i]-A[j]] + 1
                else:
                    dp[A[i], A[j]] = 2
                
                res = max(res, dp[A[i], A[j]])
                
        return res if res > 2 else 0


class Solution:
    def lenLongestFibSubseq(self, x: List[int]) -> int:
        def func(a,b):
            if (a,b) in dp:return dp[a,b]
            ans=1
            if (a+b) in f:ans=1+func(b,a+b)
            dp[a,b]=ans
            return ans
        l=len(x)
        f=set(x)
        dp={}
        ma=2
        for i in range(l):
            a=x[i]
            for j in range(i+1,l):
                b=x[j]
                ma=max(1+func(a,b),ma)
        return ma if ma>2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {x:i for i, x in enumerate(A)}
        m = collections.defaultdict(lambda:2)
        res = 0
        for i2 in range(2, len(A)):
            for i0 in range(i2):
                x1 = A[i2] - A[i0]
                if x1 <= A[i0]:
                    break
                if x1 in index:
                    i1 = index[x1]
                    m[(i1, i2)] = m[(i0, i1)] + 1
                    res = max(res, m[(i1, i2)])
        return res
        

                    

        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        fibHash = {} 
        ans = 0
        
        n = len(A)
        for i in range(1, n):
            for j in reversed(range(i)):
                f1 = A[i] - A[j]
                size = fibHash[(A[j], A[i])] = fibHash.get((f1, A[j]), 1) + 1                
                ans = max(ans, size)
                
        return ans if ans > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        mem = collections.defaultdict(Counter)
        ans = 0
        for i in range(0, n):
            for j in range(i-1, -1, -1):
                dij = A[i] - A[j]
                djk = A[j] - dij
                if djk in mem[A[j]]:
                    mem[A[i]][dij] = 1 + mem[A[j]][djk]
                else:
                    mem[A[i]][dij] = 2
                ans = max(ans, mem[A[i]][dij])
        # print(mem)
        if ans < 3:
            return 0
        return ans

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        def memo(f):
            dic = {}
            def fa(*a):
                if a not in dic:
                    dic[a] = f(*a)
                return dic[a]
            return fa
        
        cache = {val:idx for idx,val in enumerate(A)}
        
        @memo
        def leng(i,j):
            if A[i]+A[j] not in cache:
                return 2
            return 1 + leng(j, cache[A[i]+A[j]])
        
        rec = 0
        for j in range(len(A)):
            for i in range(j):
                rec = max(rec, leng(i,j))
        
        return rec if rec>2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        setA = set(A)
        answer = 0
        max_ = A[-1]
        visited = set()
        for i in range(len(A)-1):
            curr1 = A[i]
            for j in range(i+1, len(A)):
                curr2 = A[j]
                if (curr1, curr2) in visited:
                    continue
                visited.add((curr1, curr2))
                sum_ = curr1 + curr2
                l = 2 if sum_ in setA else 0
                while sum_ in setA and sum_ <= max_:
                    curr1, curr2 = curr2, sum_
                    sum_ = curr1 + curr2
                    visited.add((curr1, curr2))
                    l += 1

                answer = max(answer, l)
                curr1 = A[i]
        
        return answer

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        indexDict = {a:index for index,a in enumerate(A)}
        indexToLength = {}
        aLength = len(A)
        def computeMaxFibonacci(i,j):##gives the value of the longest sequence that starts with A[i] and A[j]. We assume that i < j. We are told it is strictly increasing so we are going to get monotonically decreasing sequences.
            if (i,j) in indexToLength:
                return indexToLength[(i,j)]
            else:
                first = A[i]
                second = A[j]
                second += first
                first = second-first
                if second in indexDict:
                    answer = 1+computeMaxFibonacci(j,indexDict[second])
                else:
                    answer = 2
                indexToLength[(i,j)] = answer
                return answer
        maxFib = 0   
        for i in range(aLength):
            for j in range(i+1,aLength):##we have to ensure that i < j.
                maxFib = max(maxFib,computeMaxFibonacci(i,j))
        ##print(indexToLength)
        return maxFib if maxFib >= 3 else 0##however it isn't as simple as returning maxFib because if it happens to be 2, then we need to return 0 per conditions of problem. Need to always consider test cases that would give variety of outputs.
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dp = collections.defaultdict(lambda: 2)
        ret, idx = 0, {A[0]:0}
        for j in range(1, len(A) -1):
            idx[A[j]] = j
            
            for i in range(j+1, len(A)):
                diff = A[i] - A[j]

                if diff >= A[j]:
                    break
                elif diff not in idx:
                    continue
                dp[j,i] = dp[idx[diff], j] +1
                ret = max(ret, dp[j,i])
        return ret


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        setA = set(A)
        answer = 0
        max_ = A[-1]
        visited = set()
        queue = collections.deque()
        for i in range(len(A)-1):
            curr1 = A[i]
            for j in range(i+1, len(A)):
                curr2 = A[j]
                if curr1 + curr2 in setA:
                    queue.append((curr1, curr2))

        while queue:
            num1, num2 = queue.popleft()
            if (num1, num2) in visited:
                continue

            visited.add((num1, num2))
            sum_ = num1 + num2
            l = 2
            while sum_ in setA and sum_ <= max_:
                num1, num2 = num2, sum_
                sum_ = num1 + num2
                visited.add((num1, num2))
                l += 1

            answer = max(answer, l)
            
        return answer

from typing import List
from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        result = 0
        starterAtIdx = [] # starterAtIdx[i] = {numbers}, where each next num is A[i] + A[j] where j < i
        fullSeqAtIdx = [] # fullSeqAtIdx[i] = {num: length}, where num is next number in seq of length
        for idx, num in enumerate(A):
            starter = set()
            fullSeq = defaultdict(int)
            for j in range(0, idx):
                prevNum = A[j]
                if num in starterAtIdx[j]:
                    fullSeq[prevNum + num] = max(fullSeq[prevNum + num], 3)
                if num in fullSeqAtIdx[j]:
                    fullSeq[prevNum + num] = max(fullSeq[prevNum + num], 1 + fullSeqAtIdx[j][num])
                result = max(result, fullSeq[prevNum + num])
                starter.add(num + prevNum)
            starterAtIdx.append(starter)
            fullSeqAtIdx.append(fullSeq)
        return result

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        seen,n={},len(A)
        A_set=set(A)
        def find_lens(ind,prev,curr):
            if ind==n:
                return 0
            key=(prev,curr)
            if key in seen:
                return seen[key]
            ans=0
            if prev+curr in A_set:
                for i in range(ind,n):
                    if curr+prev==A[i]:
                        ans=max(ans,find_lens(i+1,curr,A[i])+1)
            seen[key]=ans
            return ans
        ans=0
        for i in range(n-3):
            for j in range(i+1,n-2):
                ans=max(ans,find_lens(j+1,A[i],A[j]))
        return ans+2 if ans!=0 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        a = set(A)
        cache = {}
        ans = 0
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                ans = max(ans, self.helper(a, A[i], A[j], cache))
        # print(cache)
        return ans if ans > 2 else 0
                
    def helper(self, a, n1, n2, cache):
        if (n1, n2) not in cache:
            if n1+n2 not in a:
                cache[(n1, n2)] = 2
            else:
                cache[(n1, n2)] = self.helper(a, n2, n1+n2, cache) + 1
        return cache[(n1, n2)]
            


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        record = {}
        for i, a in enumerate(A):
            record[a] = i
        
        adj = {}
        for i in range(len(A)-2):
            for j in range(i+1, len(A)-1):
                if (A[i] + A[j]) in record:
                    adj[(i,j)] = (j, record[A[i]+A[j]])
        
        mem = {}
        def helper(i,j):
            if (i,j) in mem:
                return mem[(i,j)]
            else:
                if (i,j) in adj:
                    res = 1 + helper(adj[(i,j)][0],adj[(i,j)][1])
                    mem[(i,j)] = res
                    return res
                else:
                    mem[(i,j)] = 2
                    return 2
        res = 0
        for i in range(len(A)-2):
            for j in range(i+1, len(A)-1):
                res = max(res, helper(i,j))
        if res >= 3:
            return res
        else:
            return 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        max_l = 0
        list_poss = [{} for i in range(len(A))]
        for i in range(len(A) - 1):
            for j in range(i+1):
                if not (A[i+1] + A[j]) in list_poss[i+1]:
                    list_poss[i+1][A[i+1] + A[j]] = 2
                if A[i+1] in list_poss[j]:
                    if not(A[i+1] + A[j]) in list_poss[i+1]:
                        list_poss[i+1][A[i+1] + A[j]] = list_poss[j][A[i+1]] + 1
                    else:
                        if list_poss[j][A[i+1]] + 1 > list_poss[i+1][A[i+1] + A[j]]: 
                            list_poss[i+1][A[i+1] + A[j]] = list_poss[j][A[i+1]] + 1
                    if list_poss[i+1][A[i+1] + A[j]] > max_l:
                        max_l = list_poss[i+1][A[i+1] + A[j]]
                        
#            print(list_poss[i+1])
                        
        return max_l

from functools import lru_cache
from bisect import bisect_left

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        
        @lru_cache(None)
        def fib(p1, p2, i):
            prevsum = p1 + p2
            i = bisect_left(A, prevsum)
            if i < n and A[i] == prevsum:
                return 1 + fib(p2, A[i], i+1)
            return 0
                
        
        res = 0
        for i in range(n-2):
            for j in range(i+1, n-1):
                curres = fib(A[i], A[j], j+1)
                if curres:
                    res = max(res, 2+curres)
        return res

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dp = {}
        
        for i in range(1, len(A)):
            for j in range(i):
                dp[(A[j], A[i])] = max(dp.get((A[j], A[i]), 2), dp.get((A[i]-A[j], A[j]), 1)+1)
                
        res = max(dp.values())
        return res if res>2 else 0


from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        maps = {num:i for i, num in enumerate(A)}
        
        n = len(A)
        dp = defaultdict(lambda: 2)
        max_len = 0
        for i in range(2, n):
            for j in range(i):
                diff = A[i] - A[j]
                if diff in maps and diff < A[j]:
                    idx = maps[diff]
                    dp[j, i] = max(dp[j, i], dp[idx, j] + 1)          
                    max_len = max(dp[j, i], max_len)

        
        
        return max_len if max_len > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        nums = {}
        for i, num in enumerate(A):
            nums[num] = i

        def dfs(prev, cur, visit):
            if (prev,cur) in visit:
                return visit[(prev, cur)]
            
            if prev == -1:
                res = 0
                for i in range(len(A)):
                    for j in range(i+1, len(A)):
                        if A[i]+A[j] in nums:
                            res = max(res, 1+dfs(i,j,visit))
                return res
            
            if A[prev] + A[cur] in nums:
                visit[(prev,cur)] = 1 + dfs(cur, nums[A[prev]+A[cur]], visit)
            else:
                visit[(prev,cur)] = 1
            return visit[(prev,cur)]
        
        return dfs(-1,-1,{})

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        d = {}
        s = set(A)
        for j in range(n):
            for i in range(j):
                if (A[j] - A[i]) in s and (A[j] - A[i]) < A[i]:
                    d[(A[i], A[j])] = d.get((A[j] - A[i], A[i]), 2) + 1
        #print(d)            
        return max(d.values() or [0])

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        nums = {}
        for i, num in enumerate(A):
            nums[num] = i

        def dfs(prev, cur, visit):
            if (prev,cur) in visit:
                return visit[(prev, cur)]
            
            if A[prev] + A[cur] in nums:
                visit[(prev,cur)] = 1 + dfs(cur, nums[A[prev]+A[cur]], visit)
            else:
                visit[(prev,cur)] = 1
            return visit[(prev,cur)]
        
        visit = {}
        res = 0
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                if A[i] + A[j] in nums:
                    res = max(res, 1+dfs(i, j, visit))
        return res

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        '''
        dp(i, j): Maximum length of Fib sequence ending at A[i] & A[j]
        dp(i, j) = dp(k, j) + 1
        '''
        
        cache = set(A)
        dp = collections.defaultdict(int)
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                if A[j] - A[i] in cache and A[j] - A[i] < A[i]:
                    dp[(A[i], A[j])] = dp.get((A[j] - A[i], A[i]), 2) + 1       
        return max(list(dp.values()) + [0])        


from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        A_indices = {a: i for i, a in enumerate(A)}
        lengths = defaultdict(lambda: 2)
        def get_value(i, j):
            if (i, j) in memo:
                return memo[i, j]
            # search for A[i] + A[j] in A
            if A[i] + A[j] in A_indices:
                memo[i, j] = 1 + get_value(j, A_indices[A[i] + A[j]])
                self.best = max(self.best, memo[i, j])
            else:
                memo[i, j] = 2
            return memo[i, j]
        
        best = 2
        
        for i in range(len(A) - 3, -1, -1):
            for j in range(len(A) - 2, i, -1):
                if A[i] + A[j] in A_indices:
                    lengths[i, j] = 1 + lengths[j, A_indices[A[i] + A[j]]]
                    best = max(best, lengths[i, j])

        return best if best > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        indices = {n: i for i, n in enumerate(A)}
        d = defaultdict(lambda: 2)
        ans = 0
        for k, n in enumerate(A):
            for j in range(k-1, 0, -1):
                m = n - A[j]
                if m  not in indices:
                    continue
                i = indices[m]
                if i >= j:
                    break
                d[k, j] = d[j, i] + 1
                ans = max(ans, d[k, j])
        return ans

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        fibSeqs = {}
        values = set(arr)

        for i in range(len(arr)):
            for j in range(i-1, -1, -1):
                a = arr[i] - arr[j]
                if a >= arr[j]:
                    break
                if a in values:
                    fibSeqs[arr[j], arr[i]] = fibSeqs.get((a, arr[j]), 2) + 1

        return max(fibSeqs.values() or [0])

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        # index = {a:i for i, a in enumerate(A)}
        candidates = set(A)
        dp = {}
        N = len(A)
        ans = 0
        for r in range(N):
            for l in range(r - 1):
                if A[l] > A[r] // 2:
                    break
                if A[r] - A[l] in candidates:
                    val = dp[(A[r] - A[l], A[r])] = dp.get((A[l], A[r] - A[l]), 2) + 1
                    ans = max(ans, val)
        return ans if ans >= 3 else 0


from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        d = defaultdict(lambda: 1)
        set_A = set(A)
        
        for first in range(len(A)):
            for second in range(first + 1, len(A)):
                if A[second] - A[first] in set_A and A[first] > A[second] - A[first]:
                    d[A[first], A[second]] = d[A[second] - A[first], A[first]] + 1
        
        if len(d.values()) == 0:
            return 0
        ret = max(d.values()) + 1
        return ret if ret >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        # # straight forward N^2log(M)
        # n = len(A)
        # s = set()
        # for i in A:
        #     s.add(i)
        # res = 0
        # ll = 0
        # for i in range(n):
        #     for j in range(i+1,n):
        #         f1 = A[i]
        #         f2 = A[j]
        #         if f1+f2 in s:
        #             ll = 2
        #         while f1+f2 in s:
        #             ll += 1
        #             tmp = f2
        #             f2 = f1+f2
        #             f1 = tmp
        #         res = max(res,ll)
        # return res
        
        # # DP N^2 time N^2 space using std. dp array, if using two key dict as dp 
        # n = len(A)
        # d = {}
        # for i in range(n):
        #     d[A[i]] = i
        # dp = [[0]*n for i in range(n)]
        # res = 0
        # for i in range(n):
        #     for j in range(i+1,n):
        #         tar = A[i]+A[j]
        #         if tar in d:
        #             k = d[tar]
        #             dp[j][k] = max(dp[j][k], dp[i][j]+1, 3)
        #             res = max(res,dp[j][k])
        #     # print(res,i,j,dp)
        # return res
        
        # DP using using two key dict as dp , N^2 time NlogM space
        n = len(A)
        d = {}
        for i in range(n):
            d[A[i]] = i
        dp = {}
        res = 0
        for i in range(n):
            for j in range(i+1,n):
                tar = A[i]+A[j]
                if tar in d:
                    k = d[tar]
                    dp[(j,k)] = max(dp.get((i,j),2)+1, dp.get((j,k),2))
                    res = max(res,dp[(j,k)])
            # print(res,i,j,dp)
        return res
                    
                    
                


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        dp = [[2] * n for _ in range(n)]

        idxs = {num: i for i, num in enumerate(A)}

        result = 0
        for j in range(2, n):
            for i in range(1, j):
                target = A[j] - A[i]
                if target in idxs and target < A[i]:
                    # A[j] - A[i] 在 A 中且 在 A[i] 的左方
                    dp[i][j] = dp[idxs[target]][i] + 1
                    result = max(result, dp[i][j])

        return result


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n=len(A)
        Aset=set(A)
        ans=0
        dp={}
        for i in range(1,n):
            for j in range(i):
                diff=A[i]-A[j]
                if diff < A[j] and diff in Aset:
                    dp[(A[j],A[i])]=dp.get((diff, A[j]),2)+1
                    ans=max(ans, dp[(A[j],A[i])])
        return ans

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dp = [[2]*len(A) for _ in range(len(A))]
        d = {}
        for i, num in enumerate(A):
            d[num] = i
        
        res = 2
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                diff = A[j] - A[i]
                if diff in d and d[diff] < i:
                    dp[i][j] = dp[d[diff]][i] + 1
                    res = max(res, dp[i][j])
        
        return res if res>=3 else 0

# class Solution:
#   def lenLongestFibSubseq(self, A: List[int]) -> int:
#     aSet = set(A)
#     ans = 0
#     for i in range(len(A)):
#       for j in range(i+1, len(A)):
#         x, y = A[j], A[i] + A[j]
#         length = 2
#         while y in aSet:
#           x, y = y, x + y
#           length += 1
#         ans = max(ans, length)
#     return ans if ans >= 3 else 0

class Solution:
  def lenLongestFibSubseq(self, A: List[int]) -> int:
    aSet = set(A)
    dp = collections.defaultdict(int)
    ans = 0
    for i in range(len(A)):
      for j in range(i):
        if A[i] - A[j] < A[j] and A[i] - A[j] in aSet:
          dp[(A[j], A[i])] = dp.get((A[i] - A[j], A[j]), 2) + 1        
        
    return max(dp.values() or [0])

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dp = collections.defaultdict(int)
        s = set(A)
        
        for j in range(len(A)):
            for i in range(j):
                if A[j]-A[i] < A[i] and A[j]-A[i] in s:
                    dp[(A[i], A[j])] = dp.get((A[j]-A[i], A[i]), 2) + 1
        
        return max(dp.values() or [0])

class Solution:
    # dp, time O(n^2), space O(n^2)
    '''dp[a, b] represents the length of fibo sequence ends up with (a, b)
Then we have dp[a, b] = (dp[b - a, a] + 1) or 2
    '''
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        dp = collections.defaultdict(int)
        st = set(A)
        for i in range(n):
            for j in range(i + 1, n):
                if A[j] - A[i] < A[i] and A[j] - A[i] in st:
                    dp[A[i], A[j]] = dp.get((A[j] - A[i], A[i]), 2) + 1
        return max(dp.values() or [0])

import collections
class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dict1 = collections.defaultdict(lambda :2)
        L = len(A)
        set_A = set(A)
        if L<3:
            return 0
        d = 2
        for i,A_i in enumerate(A):
            for j in range(i,0,-1):
                if A_i-A[j]>A[j]:
                    break
                elif A_i-A[j] in set_A:
                    dd = dict1[A_i-A[j],A[j]]+1
                    dict1[A[j],A_i] = dd
                    d = max(d,dd)
        return d if d>2 else 0
                
        
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        # https://blog.csdn.net/fuxuemingzhu/article/details/82715323
        n = len(A)
        m = dict()
        for i, a in enumerate(A):
            m[a] = i
        res = 0
        # dp[i][j] := max len of seq ends with A[i], A[j]
        dp = [[2 for i in range(n)] for j in range(n)]
        for j in range(n):
            for k in range(j + 1, n):
                a_i = A[k] - A[j]
                if a_i >= A[j]:
                    break
                if a_i in m:
                    i = m[a_i]
                    dp[j][k] = dp[i][j] + 1
                    res = max(res, dp[j][k])
        return res

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        dp = collections.defaultdict(int)
        
        for j in range(len(A)):
            for i in range(j):
                if(A[j]-A[i]<A[i] and (A[j]-A[i]) in s):
                    dp[(A[i], A[j])] = dp.get((A[j]-A[i], A[i]), 2)+1
        return max(dp.values() or [0])

from collections import defaultdict
class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        
        dp = defaultdict(int)
        s = set(A)
        for i in range(len(A)):
            for j in range(i):
                if A[i] - A[j] < A[j] and A[i] - A[j] in s:
                    dp [(A[i], A[j])] = dp.get((A[j],A[i]-A[j]),2) + 1
                    
        return max(dp.values()) if dp else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        indexes = {n: i for i, n in enumerate(A)}
        dp, ans = collections.defaultdict(lambda: 2), 0
        
        for i, n in enumerate(A):
            for j in range(i):
                idx = indexes.get(n - A[j], None)
                if idx is not None and idx < j:
                    cand = dp[j, i] = dp[idx, j] + 1
                    ans = max(ans, cand)
        return ans if ans >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s=set(A)
        n = len(A)
        result = 0
        for i in range(n-1):
            for j in range(i+1,n):
                a,b = A[i],A[j]
                count = 2
                while a+b in s:
                    a,b= b,a+b
                    count+=1
                    result=max(count,result)
                    
        return result if result>2 else 0 
                


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        s = set(A)
        n = len(A)
        result = 0
                  
        for i in range(n-1):
            for j in range(i+1, n):
                a, b = A[i], A[j]
                count = 2
                while a+b in s:
                    a, b = b, a+b
                    count += 1
                    result = max(result, count)
                    
        return result if result > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        res = 0
        for i in range(len(A) - 2):
            for j in range(i+1, len(A) - 1):
                a, b = A[i], A[j]
                cnt = 2
                while a+b in s:
                    a, b = b, a+b
                    cnt += 1
                    res = max(res, cnt)
                    
        return res

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        # 1. Brutal Force
        # l = ans = 0
        # mapA = set(a)
        # for i in range(len(A)):
        #     for j in range(i+1, len(A)):
        #         x, y = A[j], A[i] + A[j]
        #         l = 2
        #         while y in mapA:
        #             x, y = y, x + y
        #             l += 1
        #         ans = max(ans, l)
        # return ans if ans >= 3 else 0
    
        # 2. DP
        from collections import defaultdict
        ans = 0
        mapA = {n: i for i, n in enumerate(A)}
        dp = defaultdict(lambda: 2)
        for k, z in enumerate(A):
            for j in range(k):
                i = mapA.get(z-A[j])
                if i is not None and i < j:
                    temp = dp[(j, k)] = dp[(i, j)] + 1
                    ans = max(ans, temp)
        return ans if ans >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        # dp = {prev_val, next_val: len}
        n = len(A)
        dp = [[2] * n for _ in range(n)]
        loc = {A[0]: 0, A[1]: 1}
        longest = 0
        for k in range(2, n):
            loc[A[k]] = k
            for j in range(k):
                target = A[k] - A[j]
                if target in loc and loc[target] < j:
                    dp[j][k] = dp[loc[target]][j] + 1
                    longest = max(longest, dp[j][k])
            
        return longest
    
        '''dp = {}
        dp[(A[1], A[0] + A[1])] = 2
        for i in range(2, len(A)):
            for j in range(i):
                if (A[j], A[i]) not in dp:
                    dp[(A[i], A[j] + A[i])] = 2
                else:
                    dp[(A[i], A[j] + A[i])] = dp[(A[j], A[i])] + 1
                    del dp[(A[j], A[i])]
        longest = max(dp.values())
        
        return longest if longest > 2 else 0'''
        
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        m={}
        for i in range(len(A)):
            m[A[i]]=i
        n=len(A)
        dp=[[2]*n for _ in range(n)]
        res=0
        for j in range(n):
            for k in range(j+1,n):
                ai=A[k]-A[j]
                if ai>=A[j]:
                    break
                if ai not in m:
                    continue
                i=m[ai]
                dp[j][k]=dp[i][j]+1
                res=max(res,dp[j][k])
        return res

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {x:i for i, x in enumerate(A)}
        dp = collections.defaultdict(lambda:2)
        
        ans = 0
        for k, z in enumerate(A):
            for j in range(k):
                i = index.get(z-A[j], None)
                if i is not None and i<j:
                    cand = dp[j, k] = dp[i, j]+1
                    ans = max(ans, cand)
        
        return ans if ans>=3 else 0

class Solution(object):
    def lenLongestFibSubseq(self, A):
        index = {x: i for i, x in enumerate(A)}
        longest = collections.defaultdict(lambda: 2)

        ans = 0
        for k, z in enumerate(A):
            for j in range(k):
                i = index.get(z - A[j], None)
                if i is not None and i < j:
                    cand = longest[j, k] = longest[i, j] + 1
                    ans = max(ans, cand)

        return ans if ans >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s=set(A)
        n=len(A)
        result=0
        for i in range(n-1):
            for j in range(i+1,n):
                a,b=A[i],A[j]
                count=2
                while a+b in s:
                    a,b=b,a+b
                    count+=1
                    result=max(result,count)
        return result if result>2 else 0

class Solution:
    def lenLongestFibSubseq1(self, A: List[int]) -> int:
        mp = {}
        
        for v in A:
            mp[v] = set()
        
        result = 0
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                a = A[i]
                b = A[j]
                l = 2
                while True:
                    if b in mp[a]:
                        break
                    if l != 2:
                        mp[a].add(b) 
                    c = a + b
                    if c not in mp:
                        break
                    a, b = b, c
                    l += 1
                if l >= 3:
                    result = max(result, l)
        return result

    def lenLongestFibSubseq(self, A):
        index = {x: i for i, x in enumerate(A)}
        longest = collections.defaultdict(lambda: 2)

        ans = 0
        for k, z in enumerate(A):
            for j in range(k):
                i = index.get(z - A[j], None)
                if i is not None and i < j:
                    cand = longest[j, k] = longest[i, j] + 1
                    ans = max(ans, cand)

        return ans if ans >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {x: i for i, x in enumerate(A)}
        longest = collections.defaultdict(lambda: 2)
        
        result = 0
        for k, z in enumerate(A):
            for j in range(k):
                i = index.get(z - A[j])
                if i is not None and i < j:
                    longest[(j, k)] = longest[(i, j)] + 1
                    result = max(result, longest[(j, k)])
        
        return result if result >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        seen,n={},len(A)
        A_set=set(A)
        def find_lens(ind,prev,curr):
            if ind==n:
                return 0
            key=(prev,curr)
            if key in seen:
                return seen[key]
            ans=0
            if prev+curr in A_set:
                for i in range(ind,n):
                    if curr+prev==A[i]:
                        ans=max(ans,find_lens(i+1,curr,A[i])+1)
            seen[key]=ans
            return ans
        ans=0
        for i in range(n-3):
            for j in range(i+1,n-2):
                if A[i]+A[j] not in A_set: continue
                ans=max(ans,find_lens(j+1,A[i],A[j]))
        return ans+2 if ans!=0 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
#         d = set()
#         n = len(A)
#         for c in A:
#             d.add(c)
            
#         max_l = 0
#         for i in range(n-2):
#             for j in range(i+1, n-1):
#                 a = A[i]
#                 b = A[j]
#                 count = 0
#                 while (a+b) in d:
#                     count += 1
#                     a,b = b,a+b
#                 max_l = max(max_l, count+2)
                
#         if max_l >= 3:
#             return max_l
#         return 0
    
        dp = collections.defaultdict(int)
        s = set(A)
        for j in range(len(A)):
            for i in range(j):
                if A[j] - A[i] < A[i] and A[j] - A[i] in s:
                    dp[A[i], A[j]] = dp.get((A[j] - A[i], A[i]), 2) + 1
        return max(dp.values() or [0])

'''
----BRUTE (but is also smart)----
KEY: use a set to hold all elements of input array.
So if you find a+b in the set, you can keep moving forward and updating 1 \"jump\" forward for a-->b, b--> a+b.
Then continue. So change the if-check to a while loop.

get every pair (i,j)
    then try to find their next value in set. If found then update 
        holdj = j
        j = i+j
        i = holdj
        len++
    res = max(res,len)
return res if res>2
----big-O----
O((N^2) * logM)
N^2 to get each pair.
logM to get to the end of each fibonacci \"chain\"

----dp----
dp[a,b] = len of fib sequence ending with a,b
dp[a,b] = dp[b-a,a]+1 , if val[b]-val[a] <val[a] and (val[b]-val[a]) exists in set
        = 2            , if (val[b]-val[a],val[a]) doesnt exist in dp
return the max of all dp cells, or [0]
---big-O--
O(N^2) for nested loop.

        
'''
class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        res = 0
        if len(A)<=2:
            return 0
        find = set(A)
        for i in range(len(A)-1):
            for j in range(i+1,len(A)):
                currLen = 2
                a = A[i]
                b = A[j]
                while (a+b) in find: 
                    currLen+=1
                    holdb = b   #you're not moving along i and j, but the actual values themselves. Because you already have the values you need in the set.
                    b = a+b
                    a = holdb
                    res = max(currLen,res)
        if res>2:
            return res
        else:
            return 0
                        
                    
                    
                    
                


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        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

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s =set(A)
        res = 2
        
        for i in range(len(A) - 2):
            for j in range(i+1, len(A) - 1):
                a, b = A[i], A[j]
                cnt = 2
                while a+b in s:
                    cnt += 1
                    res = max(res, cnt)
                    a, b = b, a+b
        
        return res if res > 2 else 0

from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        # Brute Force with Set
        # Time  complexity: O(N^2 x logM), where N is the length of A, 
        # and M is the maximum value of A.
        # Space complexity: O(N)
        # S, ans = set(A), 0
        # for i in range(len(A)):
        #     for j in range(i + 1, len(A)):
        #         x, y, l = A[j], A[i] + A[j], 2
        #         while y in S:
        #             x, y = y, x + y
        #             l += 1
        #         ans = max(ans, l)
        # return ans if ans >= 3 else 0


        # Dynamic Programming
        # Time  complexity: O(N^2)
        # Space complexity: O(NlogM), where M is the largest element of A.
        index = {x: i for i, x in enumerate(A)}
        longest = defaultdict(lambda: 2)

        ans = 0
        for k, z in enumerate(A):
            for j in range(k):
                i = index.get(z - A[j], None)
                if i is not None and i < j:
                    cand = longest[j, k] = longest[i, j] + 1
                    ans = max(ans, cand)

        return ans if ans >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        S = set(A)
        res = 2
        for i in range(len(A) - 2):
            if A[i] * (res - 1) * (res - 2) > A[-1]:
                break
            for j in range(i + 1, len(A) - 1):
                cnt = 2
                a, b = A[j], A[i] + A[j]
                while b in S:
                    cnt += 1
                    a, b = b, a + b
                res = max(res, cnt)
        return res if res > 2 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        
        ret = 0
        
        a_set = set(A)
        
        for i in range(n):
            for j in range(i + 1, n):
                num_1 = A[i]
                num_2 = A[j]
                
                length = 2
                
                while num_1 + num_2 in a_set:
                    num_3 = num_1 + num_2
                    num_1 = num_2
                    num_2 = num_3
                    length += 1
                
                if length > 2:
                    ret = max(ret, length)
         
        return ret

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        N = len(A)
        dp = [[2]*N for _ in range(N)]
        a = {val:i for i, val in enumerate(A)}
        for i in range(1, len(A)):
            for j in range(i):
                diff = A[i] - A[j]
                if diff in a and a[diff] < j:
                    dp[i][j] = max(dp[i][j], dp[j][a[diff]] + 1)
        res = max([max(i) for i in dp])
        return res if res > 2 else 0
                
                
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        N = len(A)
        
        D = { num:idx for idx, num in enumerate(A) }
        dp = [ [2] * N for _ in range(N) ]
        
        for j in range(1, N):
            for i in range(j):
                if A[j] - A[i] in D and D[A[j] - A[i]] < i:
                    #print(i, j)
                    dp[i][j] = dp[ D[A[j] - A[i]] ][i] + 1
        
        res = max(map(max, dp))
        return res if res > 2 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        table = {x:i for i,x in enumerate(A)}
        longest = collections.defaultdict(lambda: 2)
        result = 0
        
        for k, a in enumerate(A):
            for j in range(k):
                i = table.get(a-A[j], None)
                if i!=None and i<j:
                    longest[j, k] = longest[i, j] + 1
                    if longest[j, k] > result: result = longest[j,k]
        
        return result if result>=3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {x: i for i, x in enumerate(A)}
        longest = collections.defaultdict(lambda: 2)
        ans=0
        for k,z in enumerate(A):
            for j in range(k):
                i=index.get(z-A[j],None)
                if i!=None and i<j:
                    cand=longest[j,k]=longest[i,j]+1
                    ans=max(ans,cand)
        return ans if ans>=3 else 0

class Solution:
    def lenLongestFibSubseq(self, 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

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dp = collections.defaultdict(int)
        s =set(A)
        n = len(A)
        ans = 2
        for j in range(n):
            for i in range(j):
                prev = A[j]-A[i]
                if prev < A[i] and prev in s:
                    dp[A[i],A[j]] = dp.get((prev,A[i]),2) + 1
                    # ans = max(ans,dp[A[j],A[i]])
        return max(list(dp.values()) or [0])
    
        # dp = collections.defaultdict(int)
        # s = set(A)
        # for j in range(len(A)):
        #     for i in range(j):
        #         if A[j] - A[i] < A[i] and A[j] - A[i] in s:
        #             dp[A[i], A[j]] = dp.get((A[j] - A[i], A[i]), 2) + 1
        # return max(dp.values() or [0])


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        # # straight forward N^2log(N)
        # n = len(A)
        # s = set()
        # for i in A:
        #     s.add(i)
        # res = 0
        # ll = 0
        # for i in range(n):
        #     for j in range(i+1,n):
        #         f1 = A[i]
        #         f2 = A[j]
        #         if f1+f2 in s:
        #             ll = 2
        #         while f1+f2 in s:
        #             ll += 1
        #             tmp = f2
        #             f2 = f1+f2
        #             f1 = tmp
        #         res = max(res,ll)
        # return res
        
        # DP N^2 time N^2 space
        n = len(A)
        d = {}
        for i in range(n):
            d[A[i]] = i
        dp = [[0]*n for i in range(n)]
        res = 0
        for i in range(n):
            for j in range(i+1,n):
                tar = A[i]+A[j]
                if tar in d:
                    k = d[tar]
                    dp[j][k] = max(dp[j][k], dp[i][j]+1, 3)
            res = max(res, max(dp[i]))
            # print(res,i,j,dp)
        return res
                    
                    
                


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        l = len(A)
        maxL = 0
        for i in range(l):
            for j in range(i+1,l):
                a,b = A[i], A[j]
                n = 2
                while a+b in s:
                    a,b = b,a+b
                    n += 1
                if n > 2 and n > maxL:
                    maxL = n
        return maxL

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        seen = set(A)
        sequence_lens = []
        
        for i in range(len(A)):
            prev_num = A[i]
            for j in range(i + 1, len(A)):
                
                curr_num = A[j]
                seq_len = 2
                #li = [prev_num, curr_num]
                while prev_num + curr_num in seen:
                    #print(f'{prev_num} + {curr_num} = {prev_num + curr_num}')
                    seq_len += 1
                    next_num = prev_num + curr_num
                    prev_num = curr_num
                    curr_num = next_num
                    #i.append(next_num)
                prev_num = A[i]
                if seq_len > 2:
                    #print(li)
                    sequence_lens.append(seq_len)
        return max(sequence_lens) if len(sequence_lens) > 0 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
       # a hash table 
        S = set(A) 
        maxLen = 0
        n=len(A)
        for i in range(0, n): 
            for j in range(i + 1, n): 

                x = A[j] 
                y = A[i] + A[j] 
                length = 2

                # check until next fib 
                # element is found 
                while y in S: 

                    # next element of fib subseq 
                    z = x + y 
                    x = y 
                    y = z
                    length += 1
                    maxLen = max(maxLen, length) 

        return maxLen if maxLen >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        
        max_length = 0
        S = set(A)
        
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                x, y = A[i], A[j]
                expected = x+y
                length = 2
                while expected in S:
                    x=y
                    y=expected
                    expected = x+y
                    length += 1
                
                if length > max_length:
                    max_length = length
                    
        return max_length if max_length >= 3 else 0


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        A_map = {x: i for i, x in enumerate(A)}
        
        M = [[2] * len(A) for _ in range(len(A))]
        
        # M[j][k] = longest fib subsequence ending with elements (A[j], A[k])
        #           = 1 + max(M[i][j]) over i, if A[i] + A[j] = A[k]
        
        best = 0
        for k in range(len(A)):
            for j in range(k):
                i = A_map.get(A[k] - A[j], None)
                if i is not None and i < j:
                    M[j][k] = M[i][j] + 1
                    best = max(best, M[j][k])
        # for row in M:
        #     print(row)
        
        return best if best >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        A_map = {x: i for i, x in enumerate(A)}
        
        M = [[2] * len(A) for _ in range(len(A))]
        
        # M[j][k] = longest fib subsequence ending with elements (A[j], A[k])
        #           = 1 + max(M[i][j]) over i, if A[i] + A[j] = A[k]
        
        best = 0
        for k in range(len(A)):
            for j in range(1, k):
                i = A_map.get(A[k] - A[j], None)
                if i is not None and i < j:
                    M[j][k] = M[i][j] + 1
                    best = max(best, M[j][k])
        # for row in M:
        #     print(row)
        
        return best if best >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {x: i for i, x in enumerate(A)}
        longest = 0
        
        board = []
        for i in range(len(A)):
            row = []
            row = [2] * len(A)
            board.append(row)
        
        for j in range(len(A)):
            for k in range(j + 1, len(A)):
                a = A[k] - A[j]
                if a < A[j]:
                    i = index.get(a, None)
                    if i != None:
                        board[j][k] = board[i][j] + 1
                        longest = max(longest, board[j][k])
                        
        return longest

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        A_map = {x: i for i, x in enumerate(A)}
        
        M = [[2] * len(A) for _ in range(len(A))]
        
        # M[j][k] = longest fib subsequence ending with elements (A[j], A[k])
        #           = 1 + max(M[i][j]) over i, if A[i] + A[j] = A[k]
        
        best = 0
        for k in range(2, len(A)):
            for j in range(1, k):
                i = A_map.get(A[k] - A[j], None)
                if i is not None and i < j:
                    M[j][k] = M[i][j] + 1
                    best = max(best, M[j][k])
        # for row in M:
        #     print(row)
        
        return best if best >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        index = {A[i]: i for i in range(len(A))}
        longest = {}
        ans = 0
        length = len(A)
        for i in range(length):
            for j in range(i):
                x = A[i] - A[j]
                m = index.get(x)
                if m is not None and m < j:
                    longest[(j, i)] = longest.get((m, j)) + 1 if longest.get((m, j)) is not None else 3
                    ans = max(ans, longest[(j, i)])
                else:
                    continue
        return ans if ans >= 3 else 0

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        ret = 0
        n = len(A)
        mapping = {v:i for i, v in enumerate(A)}
        
        for i in range(n):
            for j in range(i+1, n):
                prev_, next_ = A[j], A[i]+A[j]
                length = 2
                while next_ in mapping:
                    length += 1
                    prev_, next_ = next_, prev_+next_
                
                if length > 2:
                    ret = max(ret, length)
        
        return ret

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        val2idx = {val: i for i, val in enumerate(A)}
        longest = collections.defaultdict(lambda: 2) #defaultval为2
        longest[(0,0)] = 1
        res = 0
        for k in range(2, len(A)):
            for j in range(k):
                i = val2idx.get(A[k] - A[j], None)
                if i != None and i < j: # i < j to control increasing order
                    longest[(j,k)] = longest[(i,j)] + 1
                    res = max(res, longest[(j,k)])
        return res if res >= 3 else 0
        # 不能只用一个数字做为ending。比如[1,2,3,4].如果只用一个数字，那么end为3时候longest是3，但是end为4的时候实际上是[1,3,4],而不是[1,2,3,4],不能直接end3 + 1


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        dp = [ [2]*len(A) for i in range(len(A))]
        d= {}
        for i in range(len(A)):
            d[A[i]] = i
        ans = 2
        for i in range(1,len(A)):
            for j in range(i):
                fn  = A[i]+A[j]
                if fn in list(d.keys()) and d[fn] > i:
                    length = dp[j][i]
                    dp[i][d[fn]] = max(dp[i][d[fn]],1+length)
                    ans = max(ans,dp[i][d[fn]])
        if ans == 2:
            return 0
        return ans
        
                
        


class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        n = len(A)
        s = set(A)
        if n <= 2:
            return 0
        ans = 0
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                a, b = A[j], A[i] + A[j]
                count = 2
                while b in s:
                    count += 1
                    a, b = b, a + b
                if count > 2:
                    ans = max(ans, count)
        return ans

from collections import defaultdict

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        A_indices = {a: i for i, a in enumerate(A)}
        lengths = defaultdict(lambda: 2)        
        best = 0
        
        for k in range(len(A) - 1, 1, -1):
            i = 0
            j = k - 1
            while i < j:
                if A[i] + A[j] < A[k]:
                    i += 1
                elif A[i] + A[j] > A[k]:
                    j -= 1
                else:
                    lengths[i, j] = lengths[j, k] + 1
                    best = max(best, lengths[i, j])
                    i += 1
                    j -= 1

        return best