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.