Solution: Longest Arithmetic Subsequence

This problem asks for the length of the longest arithmetic subsequence within a given array of integers. An arithmetic subsequence is a sequence where the difference between consecutive elements is constant.

Approach: Dynamic Programming

The most efficient approach utilizes dynamic programming. We'll build a table to store the lengths of arithmetic subsequences.

State: dp[i][diff] represents the length of the longest arithmetic subsequence ending at index i with a common difference of diff.

Base Case: dp[i][diff] = 1 for all i and diff initially, as each element by itself forms an arithmetic subsequence of length 1.

Transition: For each element nums[i], we iterate through the previous elements nums[j] (where j < i). If nums[i] - nums[j] is the common difference diff, then we can extend the arithmetic subsequence ending at j by adding nums[i]. Thus, dp[i][diff] = max(dp[i][diff], dp[j][diff] + 1).

Optimization: The common difference can be negative. To avoid negative indices in our dp array, we can add a constant offset (e.g., 500) to all differences. This shifts the range of differences to non-negative values.

Final Result: The maximum value in the dp array represents the length of the longest arithmetic subsequence.

Time and Space Complexity Analysis

• Time Complexity: O(n*d), where 'n' is the length of the input array and 'd' is the range of possible differences (after offsetting). In the worst case, d could be proportional to the range of values in nums.
• Space Complexity: O(n*d), due to the 2D dynamic programming table.

Code Implementation (Python)

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return n  # Handle cases with less than 2 elements
 
        dp = {}  # Using a dictionary for efficient lookup; key: (index, diff), value: length
        max_length = 1
 
        for i in range(1, n):
            for j in range(i):
                diff = nums[i] - nums[j] + 500  # Add offset to handle negative differences
                if (j, diff) in dp:
                    dp[(i, diff)] = dp[(j, diff)] + 1
                else:
                    dp[(i, diff)] = 2  # Base case: subsequence of length 2
                max_length = max(max_length, dp[(i, diff)])
 
        return max_length
 

Code Implementation (Java)

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        if (n < 2) return n;
 
        Map<String, Integer> dp = new HashMap<>(); //Using a HashMap for efficient lookup
        int maxLength = 1;
 
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j] + 500; //Offset for negative differences
                String key = j + "," + diff;
                int length;
                if (dp.containsKey(key)) {
                    length = dp.get(key) + 1;
                } else {
                    length = 2; //Base case
                }
                dp.put(i + "," + diff, length);
                maxLength = Math.max(maxLength, length);
            }
        }
        return maxLength;
    }
}

Other languages (C++, Go, TypeScript) would follow similar logic, employing either a 2D array or a hashmap (dictionary) for efficient storage and retrieval of subsequence lengths. The core dynamic programming approach remains consistent.