1027 Longest Arithmetic Subsequence

1027 Longest Arithmetic Subsequence#

Problem#

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Note that:

  • A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

  • A sequence seq is arithmetic if seq[i + 1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

Examples#

Example 1:

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: The first group has [1,4], and the second group has [2,3].

Example 2:

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.

Constraints:#

1 <= n <= 2000
0 <= dislikes.length <= 104
dislikes[i].length == 2
1 <= ai < bi <= n
All the pairs of dislikes are unique.

Unlike the problem where the difference is given, here we need to find the difference. So we need to find the difference between each pair of numbers and then find the longest subsequence.

2-D array as dp table with the first dimension as the index of the number and the second dimension as the difference. The value of the cell is the length of the subsequence.

However, the difference can be negative, we can do two things:

  1. Add a LARGE ENOUGH number to the difference to make it positive

  2. Use a dictionary to store the difference and the length of the subsequence

Here we implement method 2.

def longestArithemeticSubsequence(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    dp = [{} for _ in range(len(nums))]
    res = 0
    for i in range(1, len(nums)):
        for j in range(i):
            diff = nums[i] - nums[j]
            dp[i][diff] = dp[j].get(diff, 1) + 1
            res = max(res, dp[i][diff])
    return res

# test
# 4 
nums = [3,6,9,12]
print(longestArithemeticSubsequence(nums))
# 3
nums = [9,4,7,2,10]
print(longestArithemeticSubsequence(nums))
# 4
nums = [20,1,15,3,10,5,8]
print(longestArithemeticSubsequence(nums))
# 2
nums = [83,20,17,43,52,78,68,45]
print(longestArithemeticSubsequence(nums))

4
3
4
2
Contents