Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
633 B
1
Indexable
Never
class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n=nums.size();
        vector<unordered_map<int,int>>dp(n);//// (index,diff)- length of ap starting from that index with this diff
        int res=2;
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                int dif=nums[i]-nums[j];
                if(dp[j].find(dif)!=dp[j].end()){
                    dp[i][dif]=dp[j][dif]+1;
                }else {
                    dp[i][dif]=2; //i and j form 2 elements
                }
                res=max(res,dp[i][dif]);
            }
        }
        return res;
    }
};
Leave a Comment