Advertisement
Iam_Sandeep

Longest Arithmetic Increasing Subsequence

Jul 1st, 2022
765
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #User function Template for python3
  2.  
  3. class Solution:
  4.     def lengthOfLongestAP(self, A, n):
  5.         B=[{} for i in range(n)]
  6.         B[0][A[0]]=1
  7.         for i in range(1,n):
  8.             for j in range(i):
  9.                 d=A[i]-A[j]
  10.                 if d in B[i]:
  11.                     B[i][d]=max(B[i][d],1+B[j].get(d,1))
  12.                 else:
  13.                     B[i][d]=B[j].get(d,1)+1
  14.         ans=[]
  15.         for i in B:
  16.             if i:
  17.                 ans.append(max(i.values()))
  18.             else:
  19.                 ans.append(0)
  20.         return max(ans)
  21.        
  22.  
  23. #{
  24. #  Driver Code Starts
  25. #Initial Template for Python 3
  26.  
  27. if __name__ == '__main__':
  28.     tc = int(input())
  29.     while tc > 0:
  30.         n = int(input())
  31.         A = list(map(int, input().split()))
  32.         ob = Solution()
  33.         ans = ob.lengthOfLongestAP(A, n)
  34.         print(ans)
  35.         tc -= 1
  36.  
  37. # } Driver Code Ends
Advertisement
RAW Paste Data Copied
Advertisement