# 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