# longest arithmetic sequence

This is a very interesting problem, of being given a sequence of integers, and finding the longest non-contiguous ordered subsequence that forms an arithmetic sequence.

It makes graceful use of DP. Let's work with this simple sequence: `[1,2,4,3]`

. The gist of the algorithm is, we have `i`

iterating from left to right:

```
1 [1,2,4,3]
2 j i
3
4 [1,2,4,3]
5 j i
6
7 [1,2,4,3]
8 j i
9
10 [1,2,4,3]
11 j i
12
13 [1,2,4,3]
14 j i
15
16 [1,2,4,3]
17 j i
```

Look at the `i j`

pattern carefully:

```
1 1 2 3 4
2 j i
3 j i
4 j i
5 j i
6 j i
7 j i
```

While this is taking place, we are computing the value deltas between i and j.

```
1 [1,2,4,3]
2 j i 2 - 1 = 1
3
4 [1,2,4,3]
5 j i 4 - 1 = 3
6
7 [1,2,4,3]
8 j i 4 - 2 = 1
9
10 [1,2,4,3]
11 j i 3 - 1 = 2
12
13 [1,2,4,3]
14 j i 3 - 2 = 1
15
16 [1,2,4,3]
17 j i 3 - 4 = -1
```

## DP table

Think about it.. what do you really want to know, at each position `i`

? The anwser is really really easy, you want to know:

### at position `i`

and with delta `d`

what's the length of the sequence with `d`

deltas?

Observe the values in our DP table carefully:

```
1 {
2 (1, 1): 2,
3 (1, 0): 2,
4 (1, -2): 2,
5 (1, -1): 2,
6 (2, 3): 2,
7 (2, 2): 2,
8 (2, 0): 2,
9 (2, 1): 2,
10 (3, 2): 2,
11 (3, 1): 3,
12 (3, -1): 2,
13 (3, 0): 2,
14 }
```

## Few variations

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

Can also drop the need for the call to `max`

at the end:

```
1 class Solution:
2 def longestArithSeqLength(self, A):
3 d, max_len = {}, 0
4 for i in range(1, len(A)):
5 for j in range(len(A)):
6 delta = A[i] - A[j]
7 s_len = d[(j, delta)] + 1 if (j, delta) in d else 2
8 max_len = max(s_len, max_len)
9 d[(i, delta)] = s_len
10 return max_len
```

Using dict.get makes reading easier:

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

Let's use itertools.product if so inclined:

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

Another way of representing the array is:

```
1 [ 1, 2, 4, 3 ]
2 1=2 0=2 2=2
3 0=2 1=2 1=3
4 -1=2 2=2 0=2
5 -2=2 3=2 -1=2
```

The columns under each position represent the deltas on the left of the `=`

sign, and the length of the subsequence on the right of the `=`

sign.