|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +Given an array A of integers, return the length of the longest arithmetic |
| 4 | +subsequence in A. |
| 5 | +
|
| 6 | +Recall that a subsequence of A is a list A[i_1], A[i_2], ..., A[i_k] with |
| 7 | +0 <= i_1 < i_2 < ... < i_k <= A.length - 1, and that a sequence B is arithmetic |
| 8 | +if B[i+1] - B[i] are all the same value (for 0 <= i < B.length - 1). |
| 9 | +
|
| 10 | +Example 1: |
| 11 | +Input: [3,6,9,12] |
| 12 | +Output: 4 |
| 13 | +Explanation: |
| 14 | +The whole array is an arithmetic sequence with steps of length = 3. |
| 15 | +
|
| 16 | +Example 2: |
| 17 | +Input: [9,4,7,2,10] |
| 18 | +Output: 3 |
| 19 | +Explanation: |
| 20 | +The longest arithmetic subsequence is [4,7,10]. |
| 21 | +
|
| 22 | +Example 3: |
| 23 | +Input: [20,1,15,3,10,5,8] |
| 24 | +Output: 4 |
| 25 | +Explanation: |
| 26 | +The longest arithmetic subsequence is [20,15,10,5]. |
| 27 | +
|
| 28 | +Note: |
| 29 | +2 <= A.length <= 2000 |
| 30 | +0 <= A[i] <= 10000 |
| 31 | +""" |
| 32 | +fromtypingimportList |
| 33 | +fromcollectionsimportdefaultdict |
| 34 | + |
| 35 | + |
| 36 | +classSolution: |
| 37 | +deflongestArithSeqLength(self,A:List[int])->int: |
| 38 | +""" |
| 39 | + Brute force O(n^2) |
| 40 | +
|
| 41 | + Let F[i][j] be the longest arith subseq ending at A[i] with step j |
| 42 | + """ |
| 43 | +F=defaultdict(lambda:defaultdict(lambda:1)) |
| 44 | +foriinrange(len(A)): |
| 45 | +forjinrange(i): |
| 46 | +delta=A[i]-A[j] |
| 47 | +F[i][delta]=F[j][delta]+1 |
| 48 | + |
| 49 | +ret=0 |
| 50 | +fordinF.values(): |
| 51 | +forvind.values(): |
| 52 | +ret=max(ret,v) |
| 53 | + |
| 54 | +returnret |
| 55 | + |
| 56 | + |
| 57 | +if__name__=="__main__": |
| 58 | +assertSolution().longestArithSeqLength([20,1,15,3,10,5,8])==4 |