Solution
Approach 1: Brute Force with Set
Intuition
Every Fibonaccilike subsequence has each two adjacent terms determine the next expected term. For example, with 2, 5
, we expect that the sequence must continue 7, 12, 19, 31
, etc.
We can use a Set
structure to determine quickly whether the next term is in the array A
or not. Because of the exponential growth of these terms, there are at most 43 terms in any Fibonaccilike subsequence that has maximum value .
Algorithm
For each starting pair A[i], A[j]
, we maintain the next expected value y = A[i] + A[j]
and the previously seen largest value x = A[j]
. If y
is in the array, then we can then update these values (x, y) > (y, x+y)
.
Also, because subsequences are only fibonaccilike if they have length 3 or more, we must perform the check ans >= 3 ? ans : 0
at the end.
Complexity Analysis

Time Complexity: , where is the length of
A
, and is the maximum value ofA
. 
Space Complexity: , the space used by the set
S
.
Approach 2: Dynamic Programming
Intuition
Think of two consecutive terms A[i], A[j]
in a fibonaccilike subsequence as a single node (i, j)
, and the entire subsequence is a path between these consecutive nodes. For example, with the fibonaccilike subsequence (A[1] = 2, A[2] = 3, A[4] = 5, A[7] = 8, A[10] = 13)
, we have the path between nodes (1, 2) <> (2, 4) <> (4, 7) <> (7, 10)
.
The motivation for this is that two nodes (i, j)
and (j, k)
are connected if and only if A[i] + A[j] == A[k]
, and we needed this amount of information to know about this connection. Now we have a problem similar to Longest Increasing Subsequence.
Algorithm
Let longest[i, j]
be the longest path ending in [i, j]
. Then longest[j, k] = longest[i, j] + 1
if (i, j)
and (j, k)
are connected. Since i
is uniquely determined as A.index(A[k]  A[j])
, this is efficient: we check for each j < k
what i
is potentially, and update longest[j, k]
accordingly.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: , where is the largest element of
A
. We can show that the number of elements in a subsequence is bounded by where is the minimum element in the subsequence.
Analysis written by: @awice.