<p>Given an array <code>nums</code> of integers, return <em>the length of the longest arithmetic subsequence in</em> <code>nums</code>.</p>

<p><strong>Note</strong> that:</p>

<ul>
	<li>A <strong>subsequence</strong> is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.</li>
	<li>A sequence <code>seq</code> is arithmetic if <code>seq[i + 1] - seq[i]</code> are all the same value (for <code>0 &lt;= i &lt; seq.length - 1</code>).</li>
</ul>

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

<pre>
<strong>Input:</strong> nums = [3,6,9,12]
<strong>Output:</strong> 4
<strong>Explanation: </strong> The whole array is an arithmetic sequence with steps of length = 3.
</pre>

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

<pre>
<strong>Input:</strong> nums = [9,4,7,2,10]
<strong>Output:</strong> 3
<strong>Explanation: </strong> The longest arithmetic subsequence is [4,7,10].
</pre>

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

<pre>
<strong>Input:</strong> nums = [20,1,15,3,10,5,8]
<strong>Output:</strong> 4
<strong>Explanation: </strong> The longest arithmetic subsequence is [20,15,10,5].
</pre>

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

<ul>
	<li><code>2 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 500</code></li>
</ul>

class Node:
    def __init__(self, val):
        self.val = val
        self.children = {}
        self.count = {}

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        N = len(nums)
        A = [None]*N

        longest = 0
        for i in range(N):
            A[i] = Node(nums[i])
            node = A[i]

            #print(i, node.val, longest)
            for j in range(i):
                diff = node.val - A[j].val
                node.children[diff] = A[j]
            
            r = self.start(node)
            if longest < r:
                longest = r

        return longest

    def start(self, node):
        longest = 0
        for diff in node.children.keys():
            longest = max(longest, self.rec(node, diff))

        return longest

    def rec(self, node, diff):
        if diff in node.count:
            return node.count[diff]

        if diff not in node.children:
            node.count[diff] = 1
            return 1
        else:
            length = self.rec(node.children[diff], diff)
            length += 1
            node.count[diff] = length
            return length

45756