Length of longest Fibonacci subarray formed by removing only one element | Python3 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
N = 100000 NEW_LINE def createHash ( hash , maxElement ) : NEW_LINE INDENT prev = 0 NEW_LINE curr = 1 NEW_LINE hash . add ( prev ) NEW_LINE hash . add ( curr ) NEW_LINE while ( curr <= maxElement ) : NEW_LINE INDENT temp = curr + prev NEW_LINE hash . add ( temp ) NEW_LINE prev = curr NEW_LINE curr = temp NEW_LINE DEDENT DEDENT def longestFibSubarray ( arr , n ) : NEW_LINE INDENT max_val = max ( arr ) NEW_LINE hash = { int } NEW_LINE createHash ( hash , max_val ) NEW_LINE left = [ 0 for i in range ( n ) ] NEW_LINE right = [ 0 for i in range ( n ) ] NEW_LINE fibcount = 0 NEW_LINE res = - 1 NEW_LINE for i in range ( n ) : NEW_LINE INDENT left [ i ] = fibcount NEW_LINE if ( arr [ i ] in hash ) : NEW_LINE INDENT fibcount += 1 NEW_LINE DEDENT else : NEW_LINE INDENT fibcount = 0 NEW_LINE DEDENT DEDENT fibcount = 0 NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT right [ i ] = fibcount NEW_LINE if ( arr [ i ] in hash ) : NEW_LINE INDENT fibcount += 1 NEW_LINE DEDENT else : NEW_LINE INDENT fibcount = 0 NEW_LINE DEDENT DEDENT for i in range ( 0 , n ) : NEW_LINE INDENT res = max ( res , left [ i ] + right [ i ] ) NEW_LINE DEDENT return res NEW_LINE DEDENT arr = [ 2 , 8 , 5 , 7 , 3 , 5 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE print ( longestFibSubarray ( arr , n ) ) NEW_LINE