Length of largest subarray of Fibonacci Numbers

Given an array arr[] of integer elements, the task is to find the length of the largest sub-array of arr[] such that all the elements of the sub-array are Fibonacci numbers.

Examples:

Input: arr[] = { 4, 2, 3, 4, 5, 8, 11 }
Output: 2
Explanation: Maximum length sub-array with all elements as Fibonacci number is {2, 3} or {5, 8}.

Input: arr[] = {4, 6, 9}
Output: 0
Explanation: None of the number is a Fibonacci number

Approach:

Traverse the array from left to right and initialize a max_length and current_length variable with 0.
If the current element is a fibonacci number then increment current_length variable and continuethe process. Otherwise, set current_length to 0.
At each step, assign max_length as max_length = max(current_length, max_length).
Print the value of max_length in the end as it will store the required result.

Below is the implementation of the above approach:

// C++ program to find the length of the
// largest subarray where every element
// is a Fibonacci number

#include <bits/stdc++.h>
using namespace std;

// A utility function that returns true if x is a perfect square
bool isPerfectSquare(int x) 
{ 
    int s = sqrt(x); 
    return (s * s == x); 
} 

// Returns true if n is a Fibonacci Number, else false
bool isFibonacci(int n) 
{ 
    // n is a Fibonacci number if one of 5*n*n + 4 or 5*n*n - 4
    // is a perfect square
    return isPerfectSquare(5 * n * n + 4) || 
           isPerfectSquare(5 * n * n - 4); 
}

// Function to return the length of the
// largest subarray where every element
// is a Fibonacci number
int contiguousFibonacciNumber(int arr[], int n)
{
    int current_length = 0;
    int max_length = 0;

    for (int i = 0; i < n; i++) {
        // Check if arr[i] is a Fibonacci number
        if (isFibonacci(arr[i]))
            current_length++;
        else
            current_length = 0;

        max_length = max(max_length, current_length);
    }

    return max_length;
}

// Driver code
int main()
{
    int arr[] = {4, 2, 3, 4, 5, 8, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << contiguousFibonacciNumber(arr, n);

    return 0;
}

Output:

Time Complexity: O(N)
Auxiliary Space Complexity: O(1)