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 1s 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