Longest Arithmetic Subsequence

#1

Leetcoode 1027

https://ide.codingblocks.com/s/361875 - this is my code, i’m getting a TLE, can this code be optimised in any way so that I don’t get TLE ?

#2

yes, try this

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int n=A.size();
        vector< vector<int> > dp(n,vector<int>(1005,0));
        int ans=0;
        for(int i=0;i<n;i++){
            
            for(int j=0;j<i;j++){
                int diff=A[i]-A[j]+500;
                int &x=dp[i][diff],&y=dp[j][diff];
                x=max(x,1+y);
                ans=max(ans,1+x);
            }
        }
        return ans;
    }
};

dp state is simple.