💡 Problem Formulation: The task is to find the length of the longest subsequence in a given sequence of natural numbers that is also a Fibonacci subsequence. For example, given an input array [1, 3, 9, 4, 7, 10, 5], the longest Fibonacci subsequence is [1, 3, 4, 7] and its length is 4.
Method 1: Dynamic Programming Approach
This method uses dynamic programming to build a table that stores the lengths of the longest Fibonacci-like subsequence ending with two numbers, say (A[i], A[j]). The algorithm runs in O(n^2) time complexity and is more efficient for smaller sequences.
Here’s an example:
def longestFibSubseq(arr):
if len(arr) < 3:
return 0
fib_dict = {(arr[i], arr[j]): 2 for i in range(len(arr)) for j in range(i + 1, len(arr))}
max_length = 0
for k in range(1, len(arr)):
for j in range(k):
if (arr[j], arr[k] - arr[j]) in fib_dict:
fib_dict[(arr[j], arr[k])] = fib_dict[arr[j], arr[k] - arr[j]] + 1
max_length = max(max_length, fib_dict[(arr[j], arr[k])])
return max_length
print(longestFibSubseq([1, 3, 9, 4, 7, 10, 5]))The output of this code snippet:
4
This function longestFibSubseq() calculates the longest Fibonacci subsequence’s length by incrementally computing maximal subsequences that end with two specific numbers. The function then returns the maximum length found.
Method 2: Brute Force Search
This approach uses brute force to generate all possible Fibonacci subsequences and then finds the longest one. It’s a straightforward method but very inefficient with a time complexity of O(2^n), making it suitable only for very small sequences.
Here’s an example:
def isFibonacci(x, y, z):
return x + y == z
def longestFibSubseq(arr):
max_length = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
for k in range(j+1, len(arr)):
current_length = 2 if isFibonacci(arr[i], arr[j], arr[k]) else 0
x, y = arr[j], arr[k]
for l in range(k+1, len(arr)):
if isFibonacci(x, y, arr[l]):
current_length += 1
x, y = y, arr[l]
max_length = max(max_length, current_length)
return max_length
print(longestFibSubseq([1, 3, 9, 4, 7, 10, 5]))The output of this code snippet:
4
The function longestFibSubseq() iterates over every possible subsequence to find Fibonacci-like order and keeps track of the longest one found, thus returning its length.
Method 3: Hashmap Optimization
This technique optimizes the brute force approach by storing seen numbers in a hashmap to access them in O(1) time. This reduces the time complexity moderately, but still not as efficient as dynamic programming for larger sequences.
Here’s an example:
def longestFibSubseq(arr):
s = set(arr)
max_length = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
x, y, length = arr[i], arr[j], 2
while x + y in s:
x, y = y, x + y
length += 1
max_length = max(max_length, length)
return max_length if max_length > 2 else 0
print(longestFibSubseq([1, 3, 9, 4, 7, 10, 5]))The output of this code snippet:
4
Instead of brute force checking each potential sequence, the longestFibSubseq() function uses a set to check if the next number in the potential Fibonacci sequence exists in the input array, leading to a reduction in the number of operations required.
Method 4: Greedy Approach with Sorting
The greedy algorithm sorts the array and constructs possible Fibonacci sequences by checking for the third number in sequence. Despite sorting, the method can still take O(n^2) time in the worst case but often performs well in practice.
Here’s an example:
def longestFibSubseq(arr):
arr.sort()
fib_dict = defaultdict(int)
max_length = 0
s = set(arr)
for j in range(len(arr)):
for i in range(j):
if arr[j] - arr[i] in s and arr[j] - arr[i] < arr[i]:
fib_dict[(arr[i], arr[j])] = fib_dict.get((arr[j] - arr[i], arr[i]), 2) + 1
max_length = max(max_length, fib_dict[(arr[i], arr[j])])
return max_length
print(longestFibSubseq([1, 3, 9, 4, 7, 10, 5]))The output of this code snippet:
4
The function longestFibSubseq() calculates the length of the longest Fibonacci-like subsequence after sorting the array, by leveraging a greedy approach and a dict to keep track of potential sequences, making processing faster.
Bonus One-Liner Method 5: Recursive Solution
This is a concise but highly inefficient solution that exhaustively explores all combinations using recursion. Its elegance is in its simplicity but suffers from a tremendous O(2^n) time complexity, making it impractical except for tiny sequences.
Here’s an example:
def fib_helper(seq, prev, last):
if not seq:
return len(last)
elif seq[0] == prev + last[-1]:
return max(fib_helper(seq[1:], seq[0], last + [seq[0]]), fib_helper(seq[1:], prev, last))
else:
return fib_helper(seq[1:], prev, last)
def longestFibSubseq(arr):
return fib_helper(arr, 0, [0])
print(longestFibSubseq([1, 3, 9, 4, 7, 10, 5]))The output of this code snippet:
4
Using recursion, the one-liner longestFibSubseq() function explores all possible subsequences and selects the longest valid Fibonacci sequence. Although elegant, its performance is not suitable for most practical applications due to the high computational cost.
Summary/Discussion
- Method 1: Dynamic Programming Approach. Efficient for small to medium sequences. High performance. Not suitable for very large sequences due to quadratic time complexity.
- Method 2: Brute Force Search. Simplest to understand. Impractical for anything but the smallest sequences due to exponential time complexity.
- Method 3: Hashmap Optimization. A better variant of brute force. Improved performance for moderate-sized sequences. Still not optimal for very large sequences.
- Method 4: Greedy Approach with Sorting. Good average-case performance. Still quadratic in the worst case, but often faster than dynamic programming in practice.
- Bonus Method 5: Recursive Solution. Elegant and simple. Highly inefficient; only useful for educational purposes or very small datasets.