algoadvance

Given a strictly increasing array arr of positive integers forming a sequence, write a function lenLongestFibSubseq that returns the length of the longest Fibonacci-like subsequence of arr.

A sequence X1, X2, ..., Xk is Fibonacci-like if:

• k >= 3
• Xi + Xi+1 = Xi+2 for all i + 2 <= k.

If there is no such sequence, return 0.

Example

Input:

arr = [1,2,3,4,5,6,7,8]

Output:

5

Explanation:

The longest subsequence that is Fibonacci-like: [1, 2, 3, 5, 8]

Clarifying Questions

1. What is the minimum length of the provided array?
   • The array will have at least 3 elements because the smallest Fibonacci sequence length k is 3.
2. Are there duplicates in the array?
   • No, the array is strictly increasing, which implies no duplicates.
3. Can the Fibonacci-like subsequence include non-consecutive elements from the array?
   • Yes, it can include any elements as long as they follow the Fibonacci property and length criteria.

Strategy

We need to find the longest subsequence within the array that follows the Fibonacci property. To solve this, we can use a dynamic programming approach:

1. Use a Set for Quick Lookup:
   • Construct a set from the array elements to enable O(1) time complexity for checking if a particular element exists.
2. Dynamic Programming Table:
   • Use a dictionary dp where dp[(i, j)] holds the length of the longest Fibonacci-like subsequence ending with elements at indices i and j.
3. Iterate and Update:
   • For each pair of indices (i, j) (where i < j), compute the previous Fibonacci element as arr[j] - arr[i] and check if it exists in the set and also comes before index i.
   • If it exists, update dp[(i, j)].
4. Track the Maximum Length:
   • Throughout the iterations, keep track of the maximum value in dp.
5. Return Result:
   • If the maximum length found is greater than or equal to 3, return it; otherwise, return 0.

Code

def lenLongestFibSubseq(arr):
    arr_set = set(arr)
    n = len(arr)
    dp = {}
    max_len = 0
    
    for i in range(n):
        for j in range(i+1, n):
            a, b = arr[i], arr[j]
            count = 2
            while a + b in arr_set:
                a, b = b, a + b
                count += 1
            if count >= 3:
                max_len = max(max_len, count)
    
    return max_len if max_len >= 3 else 0

Time Complexity

• Time Complexity:
  • The double loop runs in O(n^2), and each internal while loop may run approximately in O(n) at worst as we traverse through the array elements once. This leads us to an overall complexity of O(n^2 * n) = O(n^3) in the worst case.
• Space Complexity:
  • The additional space is used for the dictionary dp and set arr_set, which both have space complexities of O(n). Thus, the overall space complexity is O(n).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?