Welcome to Subscribe On Youtube

3708. Longest Fibonacci Subarray

Description

You are given an array of positive integers nums.

A Fibonacci array is a contiguous sequence whose third and subsequent terms each equal the sum of the two preceding terms.

Return the length of the longest Fibonacci subarray in nums.

Note: Subarrays of length 1 or 2 are always Fibonacci.

 

Example 1:

Input: nums = [1,1,1,1,2,3,5,1]

Output: 5

Explanation:

The longest Fibonacci subarray is nums[2..6] = [1, 1, 2, 3, 5].

[1, 1, 2, 3, 5] is Fibonacci because 1 + 1 = 2, 1 + 2 = 3, and 2 + 3 = 5.

Example 2:

Input: nums = [5,2,7,9,16]

Output: 5

Explanation:

The longest Fibonacci subarray is nums[0..4] = [5, 2, 7, 9, 16].

[5, 2, 7, 9, 16] is Fibonacci because 5 + 2 = 7, 2 + 7 = 9, and 7 + 9 = 16.

Example 3:

Input: nums = [1000000000,1000000000,1000000000]

Output: 2

Explanation:

The longest Fibonacci subarray is nums[1..2] = [1000000000, 1000000000].

[1000000000, 1000000000] is Fibonacci because its length is 2.

 

Constraints:

  • 3 <= nums.length <= 105
  • 1 <= nums[i] <= 109

Solutions

Solution 1: Dynamic Programming

We can use a variable $f$ to record the length of the longest Fibonacci subarray ending at the current element. Initially, $f=2$, indicating that any two elements can form a Fibonacci subarray.

Then we traverse the array starting from index $2$. For each element $nums[i]$, if it equals the sum of the previous two elements, i.e., $nums[i] = nums[i-1] + nums[i-2]$, it means the current element can be appended to the previous Fibonacci subarray, so we increment $f$ by $1$. Otherwise, it means the current element cannot be appended to the previous Fibonacci subarray, so we reset $f$ to $2$. During the traversal, we continuously update the answer $\textit{ans} = \max(\textit{ans}, f)$.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

  • class Solution {
    public int longestSubarray(int[] nums) {
        int f = 2;
        int ans = f;
        for (int i = 2; i < nums.length; ++i) {
            if (nums[i] == nums[i - 1] + nums[i - 2]) {
                ++f;
                ans = Math.max(ans, f);
            } else {
                f = 2;
            }
        }
        return ans;
    }
}


  • class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int f = 2;
        int ans = f;
        for (int i = 2; i < nums.size(); ++i) {
            if (nums[i] == nums[i - 1] + nums[i - 2]) {
                ++f;
                ans = max(ans, f);
            } else {
                f = 2;
            }
        }
        return ans;
    }
};


  • class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        ans = f = 2
        for i in range(2, n):
            if nums[i] == nums[i - 1] + nums[i - 2]:
                f = f + 1
                ans = max(ans, f)
            else:
                f = 2
        return ans


  • func longestSubarray(nums []int) int {
	f := 2
	ans := f
	for i := 2; i < len(nums); i++ {
		if nums[i] == nums[i-1]+nums[i-2] {
			f++
			ans = max(ans, f)
		} else {
			f = 2
		}
	}
	return ans
}


  • function longestSubarray(nums: number[]): number {
    let f = 2;
    let ans = f;
    for (let i = 2; i < nums.length; ++i) {
        if (nums[i] === nums[i - 1] + nums[i - 2]) {
            ans = Math.max(ans, ++f);
        } else {
            f = 2;
        }
    }
    return ans;
}

All Problems

All Solutions