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