# longest arithmetic sequence

Given a sequence of integers, find the longest non-contiguous ordered subsequence that forms an arithmetic sequence.

As you can see above, the aim is to find monotonically increasing or decreasing ordered, sequences, e.g:

```
1[1,2,3,4,5,6]
2[1,3,5]
3[2,4,6]
```

The ultimate goal is to find the length of the longest one, `6`

in this case.

To solve this, we'll use dynamic programming, where we both read and write partial results in and out of a table. We'll scan the array with a double for loop as so:

Our DP table is a 2D matrix. The `row`

represents the `delta`

between `i`

and `j`

, while the columns represent the values for `i`

and `j`

. In other words, the cells represent the values for `i`

and `j`

at their given `i - j`

delta.

It's interesting that, once again, a DP solution requires populating a data-structure where the dimensions are somewhat intangible. It's difficult to grasp that the depth dimension of the Matrix is the `delta`

between two numbers.

Please note that the `1`

s are not actually getting written into the Matrix, but are displayed for clarity.

```
1class Solution:
2 def longestArithSeqLength(self, A):
3 d = {}
4 for i in range(1, len(A)):
5 for j in range(i):
6 delta = A[i] - A[j]
7 d[(delta, i)] = d.get((delta, j), 1) + 1
8 return max(d.values())
```

Please also note that, for simplicity, we do not need to write into a 2D matrix, and instead we can simply use a dictionary with the `(delta, i)`

tuple as index lookup.

## Time and Space Complexity