Longest Arithmetic Progression

• Time : $O(n^2)$
• Space : $O(n^2)$

c++

int Solution::solve(const vector<int> &a) {
    unordered_map<int, int> mp;
    int n = a.size();
    if(n <=2) return n;
    int dp[1010][1010];
    int res = 2;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            dp[i][j] = 2;
            int who = 2 * a[i] - a[j];
            if(mp.count(who)) dp[i][j] = max(dp[i][j], 1 + dp[mp[who]][i]);
            res = max(res, dp[i][j]);
        }
        mp[a[i]] = i;
    }
    return res;
}