Length of longest Fibonacci subarray formed by removing only one element | C ++ program to find length of the longest subarray with all fibonacci numbers ; Function to create hash table to check for Fibonacci numbers ; Insert first two fibnonacci numbers ; Summation of last two numbers ; Update the variable each time ; Function to find the longest fibonacci subarray ; Find maximum value in the array ; Creating a set containing Fibonacci numbers ; Left array is used to count number of continuous fibonacci numbers starting from left of current element ; Check if current element is a fibonacci number ; Right array is used to count number of continuous fibonacci numbers starting from right of current element ; Check if current element is a fibonacci number ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100000 NEW_LINE 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 ; } } int longestFibSubarray ( int arr [ ] , int n ) { int max_val = * max_element ( arr , arr + n ) ; set < int > hash ; createHash ( hash , max_val ) ; int left [ n ] , right [ n ] ; int fibcount = 0 , res = -1 ; for ( int i = 0 ; i < n ; i ++ ) { left [ i ] = fibcount ; if ( hash . find ( arr [ i ] ) != hash . end ( ) ) { fibcount ++ ; } else fibcount = 0 ; } fibcount = 0 ; for ( int i = n - 1 ; i >= 0 ; i -- ) { right [ i ] = fibcount ; if ( hash . find ( arr [ i ] ) != hash . end ( ) ) { fibcount ++ ; } else fibcount = 0 ; } for ( int i = 0 ; i < n ; i ++ ) res = max ( res , left [ i ] + right [ i ] ) ; return res ; } int main ( ) { int arr [ ] = { 2 , 8 , 5 , 7 , 3 , 5 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << longestFibSubarray ( arr , n ) << endl ; return 0 ; }