Longitud de la subsecuencia más larga de números de Fibonacci en una array

Dada una array arr que contiene enteros no negativos, la tarea es imprimir la longitud de la subsecuencia más larga de números de Fibonacci en esta array.
Ejemplos: 
 

Entrada: arr[] = { 3, 4, 11, 2, 9, 21 } 
Salida: 3 
Aquí, la subsecuencia es {3, 2, 21} y por lo tanto la respuesta es 3.
Entrada: arr[] = { 6, 4, 10, 13, 9, 25 } 
Salida: 1 
Aquí, la subsecuencia es {1} y, por lo tanto, la respuesta es 1. 
 

Acercarse: 
 

• Cree una tabla hash que contenga todos los números de Fibonacci que se utilizarán para probar un número en tiempo O(1).
• Ahora, recorreremos la array dada.
• Incluiremos todos los números de Fibonacci que encontremos durante nuestro recorrido en la subsecuencia más larga y, por lo tanto, aumentaremos la respuesta en 1 por cada encuentro de un número de Fibonacci.
• Una vez que se ha encontrado la array inicial completa, tenemos la longitud de la subsecuencia más larga que contiene solo números de Fibonacci.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find the length
// of longest subsequence of
// Fibonacci Numbers in an Array
 
#include <bits/stdc++.h>
using namespace std;
#define N 100005
 
// Function to create hash table
// to check Fibonacci numbers
void createHash(set<int>& hash,
                int maxElement)
{
    int prev = 0, curr = 1;
    hash.insert(prev);
    hash.insert(curr);
 
    while (curr <= maxElement) {
        int temp = curr + prev;
        hash.insert(temp);
        prev = curr;
        curr = temp;
    }
}
 
// Function to find the longest
// subsequence containing
// all Fibonacci numbers
int longestFibonacciSubsequence(
    int arr[], int n)
{
    set<int> hash;
    createHash(
        hash,
        *max_element(arr, arr + n));
 
    int answer = 0;
 
    for (int i = 0; i < n; i++) {
        if (hash.find(arr[i])
            != hash.end()) {
            answer++;
        }
    }
 
    return answer;
}
 
// Driver code
int main()
{
    int arr[] = { 3, 4, 11, 2, 9, 21 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << longestFibonacciSubsequence(arr, n)
         << endl;
 
    return 0;
}

// Java program to find the length
// of longest subsequence of
// Fibonacci Numbers in an Array
import java.util.*;
 
class GFG{
static final int N = 100005;
  
// Function to create hash table
// to check Fibonacci numbers
static void createHash(HashSet<Integer> hash,
                int maxElement)
{
    int prev = 0, curr = 1;
    hash.add(prev);
    hash.add(curr);
  
    while (curr <= maxElement) {
        int temp = curr + prev;
        hash.add(temp);
        prev = curr;
        curr = temp;
    }
}
  
// Function to find the longest
// subsequence containing
// all Fibonacci numbers
static int longestFibonacciSubsequence(
    int arr[], int n)
{
    HashSet<Integer> hash = new HashSet<Integer>();
    createHash(
        hash,Arrays.stream(arr).max().getAsInt());
  
    int answer = 0;
  
    for (int i = 0; i < n; i++) {
        if (hash.contains(arr[i])) {
            answer++;
        }
    }
  
    return answer;
}
  
// Driver code
public static void main(String[] args)
{
    int arr[] = { 3, 4, 11, 2, 9, 21 };
    int n = arr.length;
  
    // Function call
    System.out.print(longestFibonacciSubsequence(arr, n)
         +"\n");
  
}
}
 
// This code contributed by Princi Singh

# Python 3 program to find the length
# of longest subsequence of
# Fibonacci Numbers in an Array
 
N = 100005
 
# Function to create hash table
# to check Fibonacci numbers
def createHash(hash,maxElement):
    prev = 0
    curr = 1
    hash.add(prev)
    hash.add(curr)
 
    while (curr <= maxElement):
        temp = curr + prev
        hash.add(temp)
        prev = curr
        curr = temp
     
# Function to find the longest
# subsequence containing
# all Fibonacci numbers
def longestFibonacciSubsequence(arr, n):
    hash = set()
    createHash(hash,max(arr))
 
    answer = 0
 
    for i in range(n):
        if (arr[i] in hash):
            answer += 1
 
    return answer
 
# Driver code
if __name__ == '__main__':
    arr = [3, 4, 11, 2, 9, 21]
    n = len(arr)
 
    # Function call
    print(longestFibonacciSubsequence(arr, n))
 
# This code is contributed by Surendra_Gangwar

// C# program to find the length
// of longest subsequence of
// Fibonacci Numbers in an Array
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG{
static readonly int N = 100005;
   
// Function to create hash table
// to check Fibonacci numbers
static void createHash(HashSet<int> hash,
                int maxElement)
{
    int prev = 0, curr = 1;
    hash.Add(prev);
    hash.Add(curr);
   
    while (curr <= maxElement) {
        int temp = curr + prev;
        hash.Add(temp);
        prev = curr;
        curr = temp;
    }
}
   
// Function to find the longest
// subsequence containing
// all Fibonacci numbers
static int longestFibonacciSubsequence(
    int []arr, int n)
{
    HashSet<int> hash = new HashSet<int>();
    createHash(hash,arr.Max());
   
    int answer = 0;
   
    for (int i = 0; i < n; i++) {
        if (hash.Contains(arr[i])) {
            answer++;
        }
    }
   
    return answer;
}
   
// Driver code
public static void Main(String[] args)
{
    int []arr = { 3, 4, 11, 2, 9, 21 };
    int n = arr.Length;
   
    // Function call
    Console.Write(longestFibonacciSubsequence(arr, n)
         +"\n");
}
}
 
// This code is contributed by sapnasingh4991

<script>
 
// Javascript program to find the length
// of longest subsequence of
// Fibonacci Numbers in an Array
 
let N = 100005;
    
// Function to create hash table
// to check Fibonacci numbers
function createHash(hash, maxElement)
{
    let prev = 0, curr = 1;
    hash.add(prev);
    hash.add(curr);
    
    while (curr <= maxElement) {
        let temp = curr + prev;
        hash.add(temp);
        prev = curr;
        curr = temp;
    }
}
    
// Function to find the longest
// subsequence containing
// all Fibonacci numbers
function longestFibonacciSubsequence(arr, n)
{
    let hash = new Set();
    createHash(hash, Math.max(...arr));
    
    let answer = 0;
    
    for (let i = 0; i < n; i++) {
        if (hash.has(arr[i])) {
            answer++;
        }
    }
    
    return answer;
}
 
// Driver code   
      let arr = [ 3, 4, 11, 2, 9, 21 ];
    let n = arr.length;
    
    // Function call
    document.write(longestFibonacciSubsequence(arr, n)
         +"\n");
   
  // This code is contributed by sanjoy_62.
</script>

3