Data-Structure_Algorithms_Coding/q4.cpp at main · Sdccoding/Data-Structure_Algorithms_Coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//Longest Arithmetic Progression

int Solution::solve(const vector<int> &A) {
    int n=A.size();
    if(n<3)
    return n;
    int ans=1;

    //Runs at O(n3) complexity
    // for(int i=0;i<n-1;i++)
    // {
    //     for(int j=i+1;j<n;j++)
    //     {
    //         int dif=A[j]-A[i];  int ls=A[j];  int cp=2;
    //         for(int k=j+1;k<n;k++)
    //         {
    //             if(A[k]-ls==dif)
    //             {
    //                 cp++;
    //                 ls=A[k];
    //             }
    //         }
    //         ans=max(ans,cp);
    //     }
    // }
    vector<unordered_map<int,int>>v(n);
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
                int dif=A[j]-A[i];
                if(v[i].find(dif)!=v[i].end())
                {
                      v[j][dif]=v[i][dif]+1;
                }
                else
                    v[j][dif]=2;
                ans=max(ans,v[j][dif]);
        }
    }

    return ans;


}