Help me out in this problem

#1

my code is giving tle on leetcode


kindly see it
o(n^2) must be accepted as per my code

#2

@aman212yadav kindly see it

#3

its not o(n^2) bro.

image
image942×384 14.7 KB

try dynamic programming…


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

#4

@aman212yadav why it is not o(n^2)

#5

there r 4 nested loops. .

#6

@aman212yadav in solution of faang same solution is there?
but they map<int,list> insplace of vector?

#7

i m not sure whats there solution is but yeah map can be used in place of 2 d vector.

#8

@aman212yadav
is there is any solution in o(n^2) approach?

#9

dp… …

#10

@aman212yadav i didnot understand your dp logic?
can you explain me ?

#11

refer this–>link

#13

@aman212yadav //can you send me number…///////

#14

@shivammishra20121999
no bro, i cant…
is the approach still not clear?

#15

@aman212yadav
no bro i didnot get it

#16

the idea is exaclty same as longest increasing subsequence.

check this out->longest ap