Longest AP
Last Updated: 14 Mar, 2021
Difficulty: Moderate
You are given an array ‘ARR’ of size ‘N’. Your task is to find a subsequence ‘S’ of ‘ARR’ such that the following conditions hold true:
1. ‘S’ must be in arithmetic progression.
2. The length of ‘S’ must be the maximum possible.
Input Format:
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.
Output Format:
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.
Constraints:
1 <= T <= 5
1 <= N <= 50
1 <= ARR[i] <= 50
Where 'ARR[i]' is element of array at index 'i'.
Time limit: 1 sec
Approach 1
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:
- Declare a variable to store the length of the longest subsequence that is in arithmetic progression, say ‘ANSWER’.
- Run a loop from ‘i’ = 0 to ‘N’ . Here ‘N’ is the length of the array.
- Run a loop from ‘j’ = ‘i’ + 1 to ‘N’.
- Call ‘findAP’ function to get the length of maximum AP starting at index ‘i’ and have a common difference as ‘ARR[j]' – 'ARR[i]’.
- Return the ‘ANSWER’.
Description of ‘findAP’ function:
This function will take three parameters :
- ‘INDEX’: An integer to keep track of the current index of the array.
- ‘DIFFERENCE’: An integer denoting the current common difference of subsequence.
- ‘ARR’: An array ‘ARR’ given in the problem.
int findAP('INDEX', ‘DIFFERENCE’, ‘ARR’):
- If 'INDEX' >= size of the array then return 0 as we have reached the end of the subsequence.
- Declare a variable to keep track of the longest AP starting at the current index, say ‘currentMax’.
- Run a loop from 'INDEX' + 1 to the size of the array
- If ‘ARR’[i] – ‘ARR’['INDEX'] equal to the index that shows we have found a valid next term of our current AP. So recursively call ‘findAP(i, ‘DIFFERENCE', ‘ARR’)’ and update ‘currentMax’ with 1 + ‘findAP(i, ‘DIFFERENCE', ‘ARR’)’.
- Return ‘currentMax’.
Approach 2
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:
- Declare a variable to store the length of the longest subsequence that is in arithmetic progression, say ‘ANSWER’.
- Declare a ‘DP’ array to store overlapping subproblems.
- Run a loop from ‘i’ = 0 to ‘N’. Here ‘N’ is the length of the array.
- Run a loop from ‘j’ = ‘i’ + 1 to ‘N’.
- Call ‘findAP’ function to get the length of maximum AP starting at index ‘i’ and have a common difference as ‘arr[j] – arr[i]’.
- Return the ‘ANSWER’.
Description of ‘findAP’ function:
This function will take four parameters :
- ‘INDEX’: An integer to keep track of the current index of the array.
- ‘DIFFERENCE’: An integer denoting the current common difference of subsequence.
- ‘ARR’: An array ‘ARR’ given in the problem,
- ‘DP’: An array to store overlapping subproblems
int findAP('INDEX', ‘DIFFERENCE’, ‘ARR’, ‘DP’):
- If 'INDEX' >= size of the array then return 0 as we have reached the end of the subsequence.
- If ‘DP’['INDEX'][‘DIFFERENCE’] != -1 then return it as we have already calculated the answer for this subproblem.
- Declare a variable to keep track of the longest AP starting at the current 'INDEX', say ‘currentMax’.
- Run a loop from 'INDEX' + 1 to the size of the array
- If ‘ARR[i]' – 'ARR['INDEX']' equal to the index that shows we have found a valid next term of our current AP. So recursively call ‘findAP('i', ‘DIFFERENCE’, ‘ARR’)’ and update ‘currentMax’ with 1 + ‘findAP('i', ‘DIFFERENCE’, ‘ARR’)’.
- Store value of ‘currentMax’ in ‘DP['INDEX'][‘DIFFERENCE’ + 50]’. We are adding 50 to ‘DIFFERENCE’ to avoid corner cases of negative difference as we can have negative common differences.
- Return ‘currentMax’.
Approach 3
The idea here is to use iterative dynamic programming here. We will calculate answers from bottom to top.
The steps are as follows:
- Declare a variable to store the length of the longest subsequence that is in arithmetic progression, say ‘ANSWER’.
- Declare a ‘DP’ array to store overlapping subproblems.
- Run a loop from ‘i’ = 0 to ‘N’ . Here ‘N’ is the length of the array.
- Run a loop from ‘j’ = ‘i’ + 1 to ‘N’.
- Calculate ‘DIFFERENCE’ as ‘ARR[j]' – ‘ARR[i]’ + 50’.
- Update ‘DP[j][DIFFERENCE]’ with maximum of 2 and 1 + ‘DP[i][DIFFERENCE]’.
- Update 'ANSWER’ as the maximum of ‘ANSWER’ and ‘DP[j][DIFFERENCE]’.
- Return the ‘ANSWER’.
