I’ve submitted the exact code as described in the Coding video but still unable to get AC. Please tell me where I’m wrong.
Unable to get AC
try dp . because of too many for loops it exceeded the time limit.
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.
dp[i][diff] =longest ap when array [0…i] is considered and common difference is diff
its becuase of input format, there are more than one test cases in input file.