Longest Arithmetic Subsequence of Given Difference

Naive Solution

A brute-force solution would involve generating all possible subsequences of the input array arr and then, for each subsequence, checking if it forms an arithmetic sequence with the given difference. We then keep track of the longest arithmetic subsequence found so far.

This approach has a time complexity of O(2^n * n), where n is the length of arr. This is because there are 2^n possible subsequences, and for each subsequence, we might need to iterate through it to check if it's an arithmetic sequence.

Optimal Solution: Dynamic Programming

We can use dynamic programming to solve this problem more efficiently. We'll use a hash map (or dictionary) to store the length of the longest arithmetic subsequence ending at each number in arr. Specifically, dp[num] will store the length of the longest arithmetic subsequence ending with the number num.

Here's the algorithm:

1. Initialize an empty hash map dp.
2. Iterate through the input array arr.
3. For each number num in arr:
   • Check if num - difference is in dp.
   • If it is, it means we can extend an existing arithmetic subsequence ending at num - difference. So the length of the longest arithmetic subsequence ending at num will be dp[num - difference] + 1.
   • If it isn't, it means num starts a new arithmetic subsequence of length 1.
   • Update dp[num] with the appropriate length.
   • Keep track of the maximum length seen so far.
4. Return the maximum length.

Example

Let's trace the example arr = [1, 5, 7, 8, 5, 3, 4, 2, 1] and difference = -2.

• 1: dp[1] = 1, max_len = 1
• 5: dp[5] = 1, max_len = 1
• 7: dp[7] = 1, max_len = 1
• 8: dp[8] = 1, max_len = 1
• 5: dp[5] = 1, max_len = 1 (no change because it's the first time 5 has created a sequence)
• 3: dp[3] = dp[5] + 1 = 2, max_len = 2
• 4: dp[4] = 1, max_len = 2
• 2: dp[2] = dp[4] + 1 = 2 if 4 existed, dp[2] = dp[4] + 1, max_len = 2
• 1: dp[1] = dp[3] + 1 = 3, max_len = 3

Continuing in this fashion:

• arr[5] = 3: dp[3] = dp[5] + 1 = 2
• arr[6] = 4: dp[4] = 1
• arr[7] = 2: dp[2] = dp[4] + 1 = 2 if dp[4] existed. max_len = 2
• arr[8] = 1: dp[1] = dp[3] + 1 = 3. max_len = 3
• arr[6] = 5: dp[5] = 1
• arr[7] = 3: dp[3] = dp[5] + 1 = 2
• arr[8] = 1: dp[1] = dp[3] + 1 = 3
• arr[9] = 4: dp[4] = 1
• arr[10] = 2: dp[2] = dp[4] + 1 = 2
• arr[11] = 1: dp[1] = dp[3] + 1 = 3
• arr[6] = 7: dp[7] = 1
• arr[7] = 5: dp[5] = dp[7] + 1 = 2
• arr[8] = 3: dp[3] = dp[5] + 1 = 3
• arr[9] = 1: dp[1] = dp[3] + 1 = 4. max_len = 4

Code Implementation (Python)

def longestArithSeq(arr, difference):
    dp = {}
    max_len = 0
    for num in arr:
        if num - difference in dp:
            dp[num] = dp[num - difference] + 1
        else:
            dp[num] = 1
        max_len = max(max_len, dp[num])
    return max_len

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the input array arr, because we iterate through the array once.
• Space Complexity: O(n), where n is the length of the input array arr, because, in the worst case, the dp hash map might store an entry for each element in arr.

Edge Cases

• Empty Array: If the input array arr is empty, the longest arithmetic subsequence has length 0. The code handles this case correctly because max_len is initialized to 0.
• No Arithmetic Sequence: If there's no arithmetic sequence, e.g., all numbers are distinct and the difference cannot be achieved, the code will return 1 because each element itself forms an arithmetic sequence of length 1.
• Large difference: The difference variable can be large, so the space used by the dp map could grow depending on the data in arr.