Encuentre la longitud de la subsecuencia similar a Fibonacci más larga

Dada una array estrictamente creciente A de enteros positivos donde, 

. La tarea es encontrar la longitud de la subsecuencia similar a Fibonacci más larga de A . Si tal subsecuencia no existe, devuelve 0 .

Ejemplos:

Entrada: A = [1, 3, 7, 11, 12, 14, 18] 
Salida: 3 
Explicación: 
La subsecuencia más larga que es similar a Fibonacci: [1, 11, 12]. Otras posibles subsecuencias son [3, 11, 14] o [7, 11, 18].

Entrada: A = [1, 2, 3, 4, 5, 6, 7, 8] 
Salida: 5 
Explicación: 
La subsecuencia más larga que es similar a Fibonacci: [1, 2, 3, 5, 8].

Enfoque ingenuo: una secuencia similar a Fibonacci es tal que tiene dos términos adyacentes que determinan el siguiente término esperado.  

Por ejemplo, con 1, 1, esperamos que la secuencia debe continuar 2, 3, 5, 8, 13, … y así sucesivamente.

• Use Set o Map para determinar rápidamente si el próximo término de la secuencia de Fibonacci está presente en la array A o no. Debido al crecimiento exponencial de estos términos, no habrá más que búsquedas log(M) para obtener el siguiente elemento en cada iteración.
• Para cada par inicial A[i], A[j] , mantenemos el siguiente valor esperado y = A[i] + A[j] y el valor más grande visto anteriormente x = A[j] . Si y está en la array, entonces podemos actualizar estos valores (x, y) -> (y, x+y) , de lo contrario, nos detendremos de inmediato.

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

// CPP implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the max Length of
// Fibonacci subsequence
int LongestFibSubseq(int A[], int n)
{
    // Store all array elements in a hash
    // table
    unordered_set<int> S(A, A + n);
 
    int maxLen = 0, x, y;
 
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
 
            x = A[j];
            y = A[i] + A[j];
            int length = 2;
 
            // check until next fib element is found
            while (S.find(y) != S.end()) {
 
                // next element of fib subseq
                int z = x + y;
                x = y;
                y = z;
                maxLen = max(maxLen, ++length);
            }
        }
    }
 
    return maxLen >= 3 ? maxLen : 0;
}
 
// Driver program
int main()
{
    int A[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << LongestFibSubseq(A, n);
    return 0;
}
 
// This code is written by Sanjit_Prasad

// Java implementation of above approach
import java.util.*;
public class GFG {
 
// Function to return the max Length of
// Fibonacci subsequence
    static int LongestFibSubseq(int A[], int n) {
        // Store all array elements in a hash
        // table
        TreeSet<Integer> S = new TreeSet<>();
        for (int t : A) {
            // Add each element into the set
            S.add(t);
        }
        int maxLen = 0, x, y;
 
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
 
                x = A[j];
                y = A[i] + A[j];
                int length = 3;
 
                // check until next fib element is found
                while (S.contains(y) && (y != S.last())) {
 
                    // next element of fib subseq
                    int z = x + y;
                    x = y;
                    y = z;
                    maxLen = Math.max(maxLen, ++length);
                }
            }
        }
        return maxLen >= 3 ? maxLen : 0;
    }
 
// Driver program
    public static void main(String[] args) {
        int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
        int n = A.length;
        System.out.print(LongestFibSubseq(A, n));
    }
}
// This code is contributed by 29AjayKumar

# Python3 implementation of the
# above approach
 
# Function to return the max Length
# of Fibonacci subsequence
def LongestFibSubseq(A, n):
 
    # Store all array elements in
    # a hash table
    S = set(A)
    maxLen = 0
 
    for i in range(0, n):
        for j in range(i + 1, n):
 
            x = A[j]
            y = A[i] + A[j]
            length = 2
 
            # check until next fib
            # element is found
            while y in S:
 
                # next element of fib subseq
                z = x + y
                x = y
                y = z
                length += 1
                maxLen = max(maxLen, length)
             
    return maxLen if maxLen >= 3 else 0
 
# Driver Code
if __name__ == "__main__":
 
    A = [1, 2, 3, 4, 5, 6, 7, 8]
    n = len(A)
    print(LongestFibSubseq(A, n))
     
# This code is contributed
# by Rituraj Jain

// C# implementation of above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to return the max Length of
    // Fibonacci subsequence
    static int LongestFibSubseq(int []A, int n)
    {
        // Store all array elements in a hash
        // table
        SortedSet<int> S = new SortedSet<int>();
        foreach (int t in A)
        {
            // Add each element into the set
            S.Add(t);
        }
        int maxLen = 0, x, y;
 
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                x = A[j];
                y = A[i] + A[j];
                int length = 3;
 
                // check until next fib element is found
                while (S.Contains(y) && y != last(S))
                {
 
                    // next element of fib subseq
                    int z = x + y;
                    x = y;
                    y = z;
                    maxLen = Math.Max(maxLen, ++length);
                }
            }
        }
        return maxLen >= 3 ? maxLen : 0;
    }
     
    static int last(SortedSet<int> S)
    {
        int ans = 0;
        foreach(int a in S)
            ans = a;
        return ans;
    }
     
    // Driver Code
    public static void Main(String[] args)
    {
        int []A = {1, 2, 3, 4, 5, 6, 7, 8};
        int n = A.Length;
        Console.Write(LongestFibSubseq(A, n));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of above approach
 
// Function to return the max Length of
// Fibonacci subsequence
function LongestFibSubseq(A, n)
{
    // Store all array elements in a hash
    // table
    var S = new Set(A);
 
    var maxLen = 0, x, y;
 
    for (var i = 0; i < n; ++i) {
        for (var j = i + 1; j < n; ++j) {
 
            x = A[j];
            y = A[i] + A[j];
            var length = 2;
 
            // check until next fib element is found
            while (S.has(y)) {
 
                // next element of fib subseq
                var z = x + y;
                x = y;
                y = z;
                maxLen = Math.max(maxLen, ++length);
            }
        }
    }
 
    return maxLen >= 3 ? maxLen : 0;
}
 
// Driver program
var A = [1, 2, 3, 4, 5, 6, 7, 8];
var n = A.length;
document.write( LongestFibSubseq(A, n));
 
// This code is contributed by famously.
</script>

5

Complejidad de tiempo: O(N ² * log(M)), donde N es la longitud de la array y M es max(A).

Espacio Auxiliar: O(N)
Enfoque Eficiente: Para optimizar el enfoque anterior, la idea es implementar Programación Dinámica . Inicializa una tabla dp, dp[a, b] que representa la longitud de la secuencia de Fibonacci y termina en (a, b). Luego actualice la tabla como dp[a, b] = (dp[b – a, a] + 1 ) o 2 

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

// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the max Length of
// Fibonacci subsequence
int LongestFibSubseq(int A[], int n)
{
    // Initialize the unordered map
    unordered_map<int, int> m;
    int N = n, res = 0;
 
    // Initialize dp table
    int dp[N][N];
 
    // Iterate till N
    for (int j = 0; j < N; ++j) {
        m[A[j]] = j;
        for (int i = 0; i < j; ++i) {
            // Check if the current integer
            // forms a fibonacci sequence
            int k = m.find(A[j] - A[i]) == m.end()
                        ? -1
                        : m[A[j] - A[i]];
 
            // Update the dp table
            dp[i][j] = (A[j] - A[i] < A[i] && k >= 0)
                           ? dp[k][i] + 1
                           : 2;
            res = max(res, dp[i][j]);
        }
    }
 
    // Return the answer
    return res > 2 ? res : 0;
}
 
// Driver program
int main()
{
    int A[] = { 1, 3, 7, 11, 12, 14, 18 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << LongestFibSubseq(A, n);
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
 
class GFG
{
 
  // Function to return the max Length of
  // Fibonacci subsequence
  static int LongestFibSubseq(int[] A, int n)
  {
 
    // Initialize the unordered map
    HashMap<Integer,Integer>m = new HashMap<>();
    int N = n, res = 0;
 
    // Initialize dp table
    int[][] dp = new int[N][N];
 
    // Iterate till N
    for (int j = 0; j < N; ++j)
    {
      m.put(A[j], j);
      for (int i = 0; i < j; ++i)
      {
 
        // Check if the current integer
        // forms a fibonacci sequence
        int k = m.containsKey(A[j] - A[i])? m.get(A[j] - A[i]):-1;
 
        // Update the dp table
        dp[i][j] = (A[j] - A[i] < A[i] && k >= 0)
          ? dp[k][i] + 1
          : 2;
        res = Math.max(res, dp[i][j]);
      }
    }
 
    // Return the answer
    return res > 2 ? res : 0;
  }
 
  // Drivers code
  public static void main(String args[]){
 
    int[] A = { 1, 3, 7, 11, 12, 14, 18 };
    int n = A.length;
    System.out.println(LongestFibSubseq(A, n));
 
  }
}
 
// This code is contributed by shinjanpatra

# Python program for the above approach
 
# Function to return the max Length of
# Fibonacci subsequence
def LongestFibSubseq(A, n):
 
    # Initialize the unordered map
    m = {}
    N, res = n, 0
 
    # Initialize dp table
    dp = [ [0 for i in range(N) ] for J in range(N) ]
 
    # Iterate till N
    for j in range(N):
        m[A[j]] = j
        for i in range(j):
           
            # Check if the current integer
            # forms a fibonacci sequence
            k = -1 if ((A[j] - A[i]) not in m) else m[A[j] - A[i]]
 
            # Update the dp table
            dp[i][j] = dp[k][i] + 1 if (A[j] - A[i] < A[i] and k >= 0) else 2
 
            res = max(res, dp[i][j])
 
    # Return the answer
    return res if res > 2 else 0
 
# Driver program
A = [ 1, 3, 7, 11, 12, 14, 18 ]
n = len(A)
print(LongestFibSubseq(A, n))
 
# This code is contributed by shinjanpatra

// C# implementation of above approach
using System;
using System.Collections.Generic;
class HelloWorld {
 
    // Function to return the max Length of
    // Fibonacci subsequence
    static int LongestFibSubseq(int[] A, int n)
    {
        // Initialize the unordered map
        var m = new Dictionary<int, int>();
 
        int N = n;
        int res = 0;
 
        // Initialize dp table
        int[, ] dp = new int[N, N];
 
        // Iterate till N
        for (int j = 0; j < N; ++j) {
            m[A[j]] = j;
            for (int i = 0; i < j; ++i) {
                // Check if the current integer
                // forms a fibonacci sequence
                int k = m.ContainsKey(A[j] - A[i])
                            ? m[A[j] - A[i]]
                            : -1;
 
                // Update the dp table
                dp[i, j] = (A[j] - A[i] < A[i] && k >= 0)
                               ? dp[k, i] + 1
                               : 2;
                res = Math.Max(res, dp[i, j]);
            }
        }
 
        // Return the answer
        return res > 2 ? res : 0;
    }
 
    // Driver program
    static void Main()
    {
        int[] A = { 1, 3, 7, 11, 12, 14, 18 };
        int n = A.Length;
        Console.WriteLine(LongestFibSubseq(A, n));
    }
}
 
// The code is contributed by Gautam goel (gautamgoel962)

<script>
 
// JavaScript program for the above approach
 
 
// Function to return the max Length of
// Fibonacci subsequence
function LongestFibSubseq(A,n)
{
    // Initialize the unordered map
    let m = new Map();
    let N = n, res = 0;
 
    // Initialize dp table
    let dp = new Array(N);
    for(let i=0;i<N;i++){
        dp[i] = new Array(N);
    }
 
    // Iterate till N
    for (let j = 0; j < N; ++j) {
        m.set(A[j],j);
        for (let i = 0; i < j; ++i) {
            // Check if the current integer
            // forms a fibonacci sequence
            let k = m.has(A[j] - A[i]) == false
                        ? -1
                        : m.get(A[j] - A[i]);
 
            // Update the dp table
            dp[i][j] = (A[j] - A[i] < A[i] && k >= 0)
                        ? dp[k][i] + 1
                        : 2;
            res = Math.max(res, dp[i][j]);
        }
    }
 
    // Return the answer
    return res > 2 ? res : 0;
}
 
// Driver program
 
let A = [ 1, 3, 7, 11, 12, 14, 18 ];
let n = A.length;
document.write(LongestFibSubseq(A, n));
 
// code is contributed by shinjanpatra
 
</script>

3

Complejidad de tiempo: O(N ² ), donde N es la longitud de la array.

Espacio Auxiliar: O(N ² )