Longest AP

Posted: 14 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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’.
Try Problem