The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains a single integer ‘N’ denoting the size of the array.
The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array.
For each test case, return the length of the longest possible subsequence of the array that is in arithmetic progression.
The output of each test case will be printed in a separate line.
1 <= T <= 5
1 <= N <= 50
1 <= ARR[i] <= 50
Where 'ARR[i]' is element of array at index 'i'.
Time limit: 1 sec
The idea here is to check all possible common differences that a subsequence can have. We will generate all possible common differences by running two loops then we will try to find the longest subsequence using the current common difference and recursion.
The steps are as follows:
Description of ‘findAP’ function:
This function will take three parameters :
int findAP('INDEX', ‘DIFFERENCE’, ‘ARR’):
The idea here is to optimize the previous approach using dynamic programming. We are calling some functions again and again so we will call them once and store their values in a ‘dp’ array.
The below diagram shows overlapping subproblems:
The steps are as follows:
Description of ‘findAP’ function:
This function will take four parameters :
int findAP('INDEX', ‘DIFFERENCE’, ‘ARR’, ‘DP’):
The idea here is to use iterative dynamic programming here. We will calculate answers from bottom to top.
The steps are as follows: