Longest Arithmetic Subsequence - Amazon Top Interview Questions

                        Solution in C++ :

unordered_map<int, int> dp[1005];
int solve(vector<int>& nums) {
    int n = nums.size();
    int ret = min(1, n);
    for (int i = 0; i < n; i++) {
        dp[i].clear();
        for (int j = 0; j < i; j++) {
            int diff = nums[i] - nums[j];
            if (dp[j].count(diff)) {
                dp[i][diff] = max(dp[i][diff], dp[j][diff] + 1);
            } else {
                dp[i][diff] = 2;
            }
            ret = max(ret, dp[i][diff]);
        }
    }
    return ret;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] nums) {
        if (nums.length == 0)
            return 0;

        HashMap<Integer, Integer>[] maps = new HashMap[nums.length];
        int res = 1;
        for (int j = 0; j != nums.length; j++) {
            final HashMap<Integer, Integer> map = maps[j] = new HashMap<>();
            for (int i = 0; i != j; i++) {
                int length = maps[i].getOrDefault(nums[j] - nums[i], 1) + 1;
                map.put(nums[j] - nums[i], length);
                res = Math.max(res, length);
            }
        }
        return res;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, arr):
        n = len(arr)
        if n <= 1:
            return n
        res = 0
        dp = defaultdict(lambda: 1)
        for i in range(1, n):
            for j in range(i):
                diff = arr[i] - arr[j]
                dp[i, diff] = dp[j, diff] + 1
                res = max(res, dp[i, diff])

        return res