# 1027. Longest Arithmetic Sequence
Given an array A of integers, return the length of the longest arithmetic subsequence in A.
Recall that a subsequence of A is a list A[i_1], A[i_2], ..., A[i_k] with 0 <= i_1 < i_2 < ... < i_k <= A.length - 1
, and that a sequence B is arithmetic if B[i+1] - B[i]
are all the same value (for 0 <= i < B.length - 1
).
Example 1:
Input: [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
Input: [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].
Example 3:
Input: [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].
# Solution
Approach 1: O(N^3)
-- for each pair of numbers, look into the rest of the array for other items.
Approach 2: O(N^2)
-- for each element in the array, store longest arithmetic sequence so far for each diff value.
# Code (Python)
Approach 1:
def longestArithSeqLength(self, nums: List[int]) -> int:
# O(N^3) TLE
longest = 2
for i, num in enumerate(nums):
for j in range(i + 1, len(nums)):
current_longest = 2
diff = num - nums[j]
target = nums[j] - diff
for k in range(j + 1, len(nums)):
if nums[k] == target:
current_longest += 1
target = nums[k] - diff
longest = max(longest, current_longest)
return longest
Approach 2:
def longestArithSeqLength(self, nums):
# O(N^2)
longest = 2
diff_and_longest = [{0: 1}] + [{} for _ in range(len(nums) - 1)]
for i, num in enumerate(nums):
if i == 0:
continue
for j in range(i):
diff = num - nums[j]
diff_and_longest[i][diff] = diff_and_longest[j][diff] + 1 if diff in diff_and_longest[j] else 2
longest = max(longest, diff_and_longest[i][diff])
return longest
# Code (C++)
Approach 1:
Approach 2: