Leetcode 1027 - Longest Arithmetic Subsequence

Understanding the problem

The problem statement on LeetCode reads as follows:

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

Plan your solution

One way to solve this problem is to use dynamic programming. We can create a table dp where dp[i][j] represents the length of the longest arithmetic subsequence ending at index i in the input array with a difference of j. Then, we can iterate through the input array and for each element, we can check the previous elements and update the dp table accordingly. Specifically, for each element A[i], we can set dp[i][A[i] - A[j]] to be the maximum of dp[i][A[i] - A[j]] and dp[j][A[i] - A[j]] + 1 for all j such that j < i and A[i] - A[j] is a valid difference. Finally, we can return the maximum value in the dp table.

Implement your solution

Now that we have a plan, let’s implement it in Python.

def longestArithSeqLength(A):
    # Initialize the dp table with all 2s
    dp = [[2] * (100001) for _ in range(len(A))]

    # Iterate through the array
    for i in range(1, len(A)):
        # Iterate through the previous elements
        for j in range(i):
            # Calculate the difference between the current element and the previous element
            diff = A[i] - A[j]
            # If the difference is valid, update the dp table
            if diff >= 0 and diff <= 100000:
                dp[i][diff] = max(dp[i][diff], dp[j][diff] + 1)

    # Return the maximum value in the dp table
    return max(max(row) for row in dp)

Test your solution

Testing is an important step in the software development process, as it helps ensure that your code is correct and works as intended. In the case of the “Longest Arithmetic Subsequence” problem, we can test our solution by running a series of test cases that cover different scenarios and edge cases.

For example, we can test our solution with an array that has no arithmetic subsequences, an array that has only one arithmetic subsequence, an array that has multiple arithmetic subsequences with different lengths and differences, and an array that has multiple arithmetic subsequences with the same length but different differences. We can also test our solution with arrays of different lengths and with different types of elements (e.g. integers, strings, etc.). By running a variety of test cases, we can gain confidence that our solution is correct and will work for all inputs.

Related:

• longest increasing subsequence
• single element in a sorted array
• replace words with solution