Encuentre el subarreglo similar a Fibonacci más largo del arreglo dado

Dado un arreglo de N elementos, la tarea es encontrar el subarreglo más largo que sea similar a Fibonacci. 
Un subarreglo similar a Fibonacci se define como un arreglo en el que: 
 

A[i]=A[i-1]+A[i-2] where i>2

and, A[1] and A[2] can be anything.

Ejemplos: 
 

Input : N = 5, arr[] = {2, 4, 6, 10, 2}
Output : 4
The sub-array 2, 4, 6, 10 is Fibonacci like.

Input : N = 3, arr[] = {0, 0, 0}
Output : 3
The entire array is Fibonacci-like.

Enfoque:
La idea es observar que cualquier array de longitud menor o igual a 2 es similar a Fibonacci. Ahora, para arrays de longitud superior a 2:
 

1. Mantenga una variable len inicializada a 2 y una variable mx para almacenar la longitud máxima hasta el momento.
2. Comience a recorrer la array desde el tercer índice.
3. Si la array tipo Fibonacci se puede extender para este índice, es decir, si a[i] = a[i-1] + a[i-2] 
   • Luego incrementa el valor de la variable len en 1.
   • De lo contrario, reinicialice la variable len a 2.
   • Almacene el máximo de mx y len en la variable mx para la iteración actual.

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

// C++ program to find length of longest
// Fibonacci-like subarray
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the length of the
// longest Fibonacci-like subarray
int longestFibonacciSubarray(int n, int a[])
{
    // Any 2 terms are Fibonacci-like
    if (n <= 2)
        return n;
     
    int len = 2;
     
    int mx = INT_MIN;
     
    for (int i = 2; i < n; i++) {
         
        // If previous subarray can be extended
        if (a[i] == a[i - 1] + a[i - 2])
            len++;
             
        // Any 2 terms are Fibonacci-like
        else
            len = 2;
             
        // Find the maximum length
        mx = max(mx, len);
    }
     
    return mx;
}
 
// Driver Code
int main()
{
    int n = 5;
    int a[] = {2, 4, 6, 10, 2};
     
    cout << longestFibonacciSubarray(n, a);
     
    return 0;
}

// Java program to find length of longest
// Fibonacci-like subarray
class GFG
{
     
    // Function to find the length of the
    // longest Fibonacci-like subarray
    static int longestFibonacciSubarray(int n, int a[])
    {
        // Any 2 terms are Fibonacci-like
        if (n <= 2)
            return n;
         
        int len = 2;
         
        int mx = Integer.MIN_VALUE;
         
        for (int i = 2; i < n; i++)
        {
             
            // If previous subarray can be extended
            if (a[i] == a[i - 1] + a[i - 2])
                len++;
                 
            // Any 2 terms are Fibonacci-like
            else
                len = 2;
                 
            // Find the maximum length
            mx = Math.max(mx, len);
        }
        return mx;
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int n = 5;
        int a[] = {2, 4, 6, 10, 2};
         
        System.out.println(longestFibonacciSubarray(n, a));
    }
}
 
// This code is contributed by Ryuga

# Python3 program to find Length of
# longest Fibonacci-like subarray
 
# Function to find the Length of the
# longest Fibonacci-like subarray
def longestFibonacciSubarray(n, a):
 
    # Any 2 terms are Fibonacci-like
    if (n <= 2):
        return n
     
    Len = 2
     
    mx = -10**9
     
    for i in range(2, n):
         
        # If previous subarray can be extended
        if (a[i] == a[i - 1] + a[i - 2]):
            Len += 1
             
        # Any 2 terms are Fibonacci-like
        else:
            Len = 2
             
        # Find the maximum Length
        mx = max(mx, Len)
     
    return mx
 
# Driver Code
n = 5
a = [2, 4, 6, 10, 2]
 
print(longestFibonacciSubarray(n, a))
 
# This code is contributed by Mohit Kumar

// C# program to find length of longest
// Fibonacci-like subarray
using System;
 
class GFG
{
     
    // Function to find the length of the
    // longest Fibonacci-like subarray
    static int longestFibonacciSubarray(int n, int[] a)
    {
        // Any 2 terms are Fibonacci-like
        if (n <= 2)
            return n;
         
        int len = 2;
         
        int mx = int.MinValue;
         
        for (int i = 2; i < n; i++)
        {
             
            // If previous subarray can be extended
            if (a[i] == a[i - 1] + a[i - 2])
                len++;
                 
            // Any 2 terms are Fibonacci-like
            else
                len = 2;
                 
            // Find the maximum length
            mx = Math.Max(mx, len);
        }
        return mx;
    }
     
    // Driver Code
    public static void Main ()
    {
        int n = 5;
        int[] a = {2, 4, 6, 10, 2};
         
        Console.WriteLine(longestFibonacciSubarray(n, a));
    }
}
 
// This code is contributed by Code_Mech.

<?php
// PHP program to find length of longest
// Fibonacci-like subarray
 
// Function to find the length of the
// longest Fibonacci-like subarray
function longestFibonacciSubarray($n, $a)
{
    // Any 2 terms are Fibonacci-like
    if ($n <= 2)
        return $n;
     
    $len = 2;
     
    $mx = PHP_INT_MIN;
     
    for ($i = 2; $i < $n; $i++)
    {
         
        // If previous subarray can be extended
        if ($a[$i] == $a[$i - 1] + $a[$i - 2])
            $len++;
             
        // Any 2 terms are Fibonacci-like
        else
            $len = 2;
             
        // Find the maximum length
        $mx = max($mx, $len);
    }
     
    return $mx;
}
 
// Driver Code
$n = 5;
$a = array(2, 4, 6, 10, 2);
     
echo longestFibonacciSubarray($n, $a);
 
// This code is contributed
// by Akanksha Rai   
?>

<script>
 
// javascript program to find length of longest
// Fibonacci-like subarray
 
     
    // Function to find the length of the
    // longest Fibonacci-like subarray
    function longestFibonacciSubarray( n,  a)
    {
        // Any 2 terms are Fibonacci-like
        if (n <= 2)
            return n;
         
        var len = 2;
         
        var mx = Number.MIN_VALUE;
  
         
        for (var i = 2; i < n; i++)
        {
             
            // If previous subarray can be extended
            if (a[i] == a[i - 1] + a[i - 2])
                len++;
                 
            // Any 2 terms are Fibonacci-like
            else
                len = 2;
                 
            // Find the maximum length
            mx = Math.max(mx, len);
        }
        return mx;
    }
     
    // Driver Code
 
        var n = 5;
        var a = [2, 4, 6, 10, 2];
         
        document.write(longestFibonacciSubarray(n, a));
   
  // This code is contributed by bunnyram19.
</script>

4

Complejidad temporal: O(N) 
Espacio auxiliar : O(1)