Longest Arithmetic Subsequence — LeetCode 1027 Python Solution

The 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.

Example

Input

nums = [3,6,9,12]

Output

4

Explanation

The whole array is an arithmetic sequence with steps of length = 3.

Python solution

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        n = len(nums)
        f = [[1] * 1001 for _ in range(n)]
        ans = 0
        for i in range(1, n):
            for k in range(i):
                j = nums[i] - nums[k] + 500
                f[i][j] = max(f[i][j], f[k][j] + 1)
                ans = max(ans, f[i][j])
        return ans

Complexity

Pattern: Binary Search

Halve the search space each step — over an array, or over the answer itself. LeetCode 1027. Longest Arithmetic Subsequence is filed here because LeetCode tags it Binary Search, which is the vocabulary this hub collects.

The binary search guide has the Python template for the pattern and the 254 LeetCode problems that use it.

Related problems