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: MEDIUM
Tags: Dynamic programming

Data structures
Skill types: Dynamic programming

Data structures

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])
				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


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:

	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:
		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:
		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:
		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:
		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 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
		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:
					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]
				x = A[j]
				y = z - x
				k = d.get(y, -1)
				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:
		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


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)
				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
		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:
					length = dp[n1][n2] + 1
					if length > dp[n2][n3]:
						dp[n2][n3] = length
						ret = max(ret, length)
		return ret


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)
		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)
		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)
		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])
					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:
		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:
					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
					ans = max(ans, B[a, b] + 2)
				if c > A[-1]:
					break
		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:
		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:
		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(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


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)
				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:
		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
					(a, b) = (b, a + b)
				max_length = max(max_length, curr_length)
		if max_length <= 2:
			return 0
		return max_length


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:
		mapA = {n: i for (i, n) in enumerate(A)}
		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:
		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)
					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:
		(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:
		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:

		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:
		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)
		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:
		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)
		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:
		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


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:

	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:
		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
		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:
		setA = set(A)
		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:
					(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:
		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:
		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 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
			while si < len(A):
				reqd_sum = A[temp_fi] + A[si]
				if reqd_sum > sum_lim:
					break
				pres = BinarySearch(A, reqd_sum)
				if 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:
		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))
		return rint


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
		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:
		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:
		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 = {}
		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:
		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
		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


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:
		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
			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:
				return maxLevel(A, var2_idx, returned_idx, level + 1)
			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:
		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:
		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
		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:
		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())
		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:
		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


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


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]
			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:
		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:
			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:
		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])
		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):
			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):
				maxFib = max(maxFib, computeMaxFibonacci(i, j))
		return maxFib if maxFib >= 3 else 0


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 = []
		fullSeqAtIdx = []
		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))
		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]
			elif (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
					elif 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]]
		return max_l


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:
		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])


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:
		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:
		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])
		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]:
					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)
		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])


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:
		n = len(A)
		m = dict()
		for (i, a) in enumerate(A):
			m[a] = i
		res = 0
		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


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:
		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:
		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


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 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:
		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
					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:
		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:
					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:
		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
				while prev_num + curr_num in seen:
					seq_len += 1
					next_num = prev_num + curr_num
					prev_num = curr_num
					curr_num = next_num
				prev_num = A[i]
				if seq_len > 2:
					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:
		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
				while y in S:
					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:
		A_map = {x: i for (i, x) in enumerate(A)}
		M = [[2] * len(A) for _ in range(len(A))]
		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])
		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:
		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)
		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:
					longest[j, k] = longest[i, j] + 1
					res = max(res, longest[j, k])
		return res if res >= 3 else 0


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


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