# 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


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.