<p>A sequence <code>x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub></code> is <em>Fibonacci-like</em> if:</p>

<ul>
	<li><code>n &gt;= 3</code></li>
	<li><code>x<sub>i</sub> + x<sub>i+1</sub> == x<sub>i+2</sub></code> for all <code>i + 2 &lt;= n</code></li>
</ul>

<p>Given a <b>strictly increasing</b> array <code>arr</code> of positive integers forming a sequence, return <em>the <strong>length</strong> of the longest Fibonacci-like subsequence of</em> <code>arr</code>. If one does not exist, return <code>0</code>.</p>

<p>A <strong>subsequence</strong> is derived from another sequence <code>arr</code> by deleting any number of elements (including none) from <code>arr</code>, without changing the order of the remaining elements. For example, <code>[3, 5, 8]</code> is a subsequence of <code>[3, 4, 5, 6, 7, 8]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,2,3,4,5,6,7,8]
<strong>Output:</strong> 5
<strong>Explanation:</strong> The longest subsequence that is fibonacci-like: [1,2,3,5,8].</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,3,7,11,12,14,18]
<strong>Output:</strong> 3
<strong>Explanation</strong>:<strong> </strong>The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= arr.length &lt;= 1000</code></li>
	<li><code>1 &lt;= arr[i] &lt; arr[i + 1] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        # Create a hash map to store value to index mappings for quick access
        value_to_index = {value: index for index, value in enumerate(arr)}
        n = len(arr)
      
        # Initialize a 2D array for dynamic programming, setting initial subsequence sizes to 2
        dp = [[2 for _ in range(n)] for _ in range(n)]
      
        # This variable will keep track of the longest fib sequence found
        longest_fib_sequence = 0
      
        # Iterate over pairs of numbers in the array to build up sequences
        for i in range(n):
            for j in range(i):
                # Find the previous number in the potential Fibonacci sequence
                difference = arr[i] - arr[j]
                # Check if the number exists in our array and precedes the second number (j)
                if difference in value_to_index and value_to_index[difference] < j:
                    # The k index refers to the position of the previous number
                    prev_index = value_to_index[difference]
                    # Update the DP table by extending the sequence found from prev_index and j
                    dp[j][i] = max(dp[j][i], dp[prev_index][j] + 1)
                    # Update the answer if a longer sequence is found
                    longest_fib_sequence = max(longest_fib_sequence, dp[j][i])
      
        return longest_fib_sequence
25400