Length of Longest Fibonacci Subsequence

dp[i][j] = dp[k][i] + 1

Extend the subsequence ending at (k, i) to include arr[j].

This dynamic programming transition extends an existing Fibonacci-like subsequence. If arr[k], arr[i] already form the end of a valid sequence, adding arr[j] increases its length by one while preserving the Fibonacci relation.

dp = [[2] * n for _ in range(n)]

Initialize the DP table where dp[i][j] stores the length of a subsequence ending with arr[i] and arr[j].

Each DP state represents a subsequence ending with arr[i] and arr[j]. Any pair of elements forms a subsequence of length two, so initializing every state to 2 establishes the base length before any Fibonacci extension occurs.

prev = arr[j] - arr[i]

Compute the value that would precede arr[i] in a Fibonacci-like relation.

For arr[i] and arr[j] to be consecutive elements of a Fibonacci-like sequence, a previous value must satisfy prev + arr[i] = arr[j]. Rearranging yields prev = arr[j] - arr[i], identifying the value required to extend the sequence.

if k < i:

Verify that the previous element occurs before arr[i].

The constraint k < i ensures that the sequence respects the array's ordering. Without this condition, the algorithm might construct invalid subsequences that reuse elements out of order.

value_to_index = {}

Create a dictionary that maps each array value to its index.

Efficient extension of Fibonacci-like subsequences requires quickly locating the index of a value. A hash map enables constant-time lookup of the previous element needed to form the Fibonacci relation.

if prev in value_to_index:

Check whether the required previous value appears in the array.

Only if this previous value exists in the array can the subsequence be extended. If it does not exist, the pair (i, j) remains a base subsequence of length two.

return longest if longest >= 3 else 0

Return the maximum length if it forms a valid sequence, otherwise return zero.

A valid Fibonacci-like subsequence must contain at least three elements. Returning zero indicates that no such sequence was found.

for j in range(n):

Iterate through the array treating j as the last element of the subsequence pair.

Fixing j as the second element of the pair allows the algorithm to evaluate all possible preceding elements i, ensuring every potential subsequence ending at j is considered.

for i in range(j):

Iterate through indices i that occur before j.

Selecting i < j ensures subsequences respect the original ordering of the array while exploring all valid pairs that could end a Fibonacci-like sequence.

k = value_to_index[prev]

Look up the index of the previous value.

Retrieving the index k allows the algorithm to reference the previously computed DP state representing the subsequence ending with arr[k] and arr[i].

value_to_index[arr[i]] = i

Record the current value and its index in the lookup dictionary.

Mapping values to indices allows the algorithm to determine whether the required previous number in a Fibonacci relation exists earlier in the array.

longest = max(longest, dp[i][j])

Update the recorded maximum subsequence length.

Updating the global maximum during iteration ensures the algorithm retains the length of the longest subsequence discovered so far.

for i in range(n):

Iterate through the array indices to populate the value-to-index map.

This loop ensures every value in the array is indexed before the dynamic programming stage begins, enabling fast lookups during DP transitions.

longest = 0

Initialize a variable to track the longest subsequence length discovered.

Maintaining the maximum length during computation avoids an additional pass through the DP table after processing all pairs.

n = len(arr)

Store the number of elements in the array.

Caching the array length avoids repeated calls to len(arr) and provides a clear reference for iteration bounds throughout the algorithm.