The objective of this article is to discuss various approaches to solve the length of the longest Fibonacci subsequence problem. In this problem, we have a strictly increasing array of positive integers. Our task is to find the length of the longest Fibonacci subsequence possible. We will solve this using Brute force and Dynamic Programming.

For example:

Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: The longest fibonacci subsequence is [1,2,3,5,8].

Input: arr = [1,3,7,11,12,14,18]
Output: 3
Explanation:  The longest fibonacci subsequences are [1,11,12], [3,11,14] or [7,11,18].

Naive Approach

Since the first two values of the Fibonacci series can have any value, we will use two nested for loops to generate all the pairs possible in the given array. These pairs act as the first two values of the Fibonacci series. We return the length of the longest Fibonacci subsequence formed by these pairs.

Algorithm

Step 1: The Outer loop traverses the array from index 0 to size - 2.
Step 2: The Inner loop traverses from index i(current outer loop index) + 1 to size -1.
Step 3: arr[outer loop index] and arr[inner loop index] are the values of the first two elements of the Fibonacci series.
Step 4: Check if the next element (sum of last two elements of the series) of the Fibonacci series is present in the array with the help of a set or map.
Step 5: If the next element is present then increment the length of the series and repeat step 4.
Step 6: If the next element is not present then compare the current length and max length.
Step 7: If the current length is greater than the max length then the max length is equal to the current length.
Step 8: Return max length.

Time and Space Complexity.

• The time complexity is O(n * n * log(m)).
• The Space complexity is O(n) because we are using a set or map to store elements.
  where n is the size of the array and m is the maximum value in the array.

Example

Let us assume that we are given an array with elements 1, 2, 3, 4, 5, 6, 7, 8.

Array -> 1 2 3 4 5 6 7 8

The possible pairs in the given array are

(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1,8)
(2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2,8)
(3, 4), (3, 5), (3, 6), (3, 7), (3, 8)
(4, 5), (4, 6), (4, 7), (4, 8)
(5, 6), (5, 7), (5,8)
(6, 7), (6, 8)
(7, 8)

The Fibonacci subsequence starting with 1 and 2 are
1 2 3 5 8
length -> 5.

The Fibonacci subsequence starting with 1 and 3 are
1 3 4 7
length -> 4.

The Fibonacci subsequence starting with 1 and 4 are
1 4 5
length -> 3.

Similarly, we will find the length of the Fibonacci subsequence for all pairs.

The length of the longest Fibonacci subsequence formed by these pairs is 5.

Implementing naive approach

• C++

#include<iostream>
#include<vector>
#include<set>


using namespace std;
int lenLongestFibSubseq(vector<int>& arr) {
        set<int> s;
        int max_length=2;
        //store the values in set s.
        for(int i=0;i<arr.size();i++){
            s.insert(arr[i]);
        }
        

        for(int i=0;i<arr.size()-1;i++){
            for(int j=i+1;j<arr.size();j++){
                int length=2,x,y,z;
                x=arr[i];//first element of fibonacci series.
                y=arr[j];//Second element of fibonacci series.
                z=arr[i]+arr[j];//next element of fibonacci series.
                while(s.find(z)!=s.end()){
                    length++;
                    x=y;//second last element of fibonacci series.
                    y=z;//last element of fibonacci series.
                    z=x+y;//next element of fibonacci series.
                }
                if(length>max_length){
                    max_length=length;
                }
            }
        }
        if(max_length>2){
        return max_length;
        }else{
            return 0;
        }
    }
    

    int main(){
    vector<int> arr{1, 2, 3, 4, 5, 6, 7, 8};
    cout<<lenLongestFibSubseq(arr);
    return 0;
    }

Output.

5

Dynamic Programming approach

The above problem can be solved efficiently using dynamic programming. In this approach, we will create a 2d array of size (n*n) where n is the size of the given array. We return the maximum value in 2d array.

The idea is as follows:

arr[i][j] represents the length of the longest Fibonacci series
ending with a[i] and a[j] where a is the given array.

Base case is:

arr[i][j] = 2

The minimum length of the Fibonacci series ending with a[j] and a[i] is 2.

The relation to compute the dp table is as follows:

arr[j][k]= 1 + arr[i][k]

where i is the index of the given array that contains value a[k] - a[j]
and a[i] is less than a[j] (a is the given array).
If no such i exists then do not update arr[j][k].

Algorithm

Step 1: Store the index of all the elements of the given array using a map.
Step 2: Create a 2-d array of size (n * n) where n is the size of the given array.
Step 3: Initialize all the elements of 2-d array with 2.
Step 4: arr[j][k] is equal to 1 + arr[i][j] where i is the index of the given array that contains value a[k] - a[j] and a[i] is less than a[j] (a is the given array).
Step 5: If index i doesnot exist then don't update arr[j][k].
Step 6: Find the maximum value in the 2-d array.
Step 7: If the maximum value is 2 then return 0.
Step 8: If the maximum value is not 2 then return the maximum value.

Time and Space Complexity.

• The time complexity is O(n * n).
• The space complexity is O(n * n) because we are using a 2-d array.

Example.

Let us assume that we are given an array with elements 1, 2, 3, 4, 5, 6, 7, 8.

Array -> 1 2 3 4 5 6 7 8

We store the index of all the elements using a map called maps.

maps:

1 -> 0
2 -> 1
3 -> 2
4 -> 3
5 -> 4
6 -> 5
7 -> 6
8 -> 7.

The first column represents the elements value and the second column represents the index of elements in the array.
The 2d array (dp) after defining and initializing looks like

2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2

we will traverse the 2d array row-wise.

for dp[0,1].
the i value is array[1]-array[0].
i is equal to 2 - 1.
i=1.
Since 1 is not smaller than 1.
No need to update the 2d array.

for dp[1,2]
the i value is arr[2]-arr[1].
i is equal to 3 - 2=1.
since 1 is smaller than 2 and is present in array
therefore dp[maps[2],maps[3]] is equal to 1 plus dp[maps[1],maps[2]]
we know that maps of 2 is 1, 3 is 2,and 1 is 0.
therefore dp[1,2]= 1 +dp[0,1]
dp[1,2]=1+2.
dp[1,2]=3.

Similarly, we will do these operations for all elements of 2d array.

After all the operations the 2d array looks like

2 2 2 2 2 2 2 2
2 2 3 2 2 2 2 2
2 2 2 3 4 2 2 2
2 2 2 2 3 3 4 2
2 2 2 2 2 3 3 5
2 2 2 2 2 2 3 3
2 2 2 2 2 2 2 3 
2 2 2 2 2 2 2 2

The maximum value in the 2d array is 5.
The final output is 5.

Implementing dynamic programming approach

• C++

#include<iostream>
#include<vector>
#include<map>


using namespace std;
int lenLongestFibSubseq(vector<int> &arr) {
        map<int,int> maps;
        for(int i=0;i<arr.size();i++){
            maps.insert(make_pair(arr[i],i));
        }
        int x=arr.size();
        int dp[x][x];//defining a 2d array.
        

        for(int i=0;i<x;i++){
            for(int j=0;j<x;j++){
                dp[i][j]=2;/*initializing all elements of 2d array with 2.*/
            }
        }
        

        int max_length=2;
        for(int i=0;i<x;i++){
            for(int j=i+1;j<x;j++){
                int k=arr[j] -arr[i];
                if(k<arr[i]){/*checking wether k is smaller than the last two elements.*/
                if(maps.find(k)!=maps.end()){
                    dp[i][j]=1+dp[maps[k]][i];
                }
                }
                if(dp[i][j]>max_length){
                    max_length=dp[i][j];
                }
            }
        }
        if(max_length>2){
            return max_length;
        }
    return 0;
    }
    

    int main(){
    vector<int> arr{1, 2, 3, 4, 5, 6, 7, 8};
    cout<<lenLongestFibSubseq(arr);
    return 0;
    }

Output

5