Longest AP

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in company
Snapdeal Ltd.

Problem statement

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:

• ‘S’ must be in arithmetic progression.

• The length of ‘S’ must be the maximum possible.

Return the maximum possible length of 'S'.

Example -

ARR = [2,8,4,13,6] The longest subsequence that is possible here is [2,4,6] which has length '3'.

Detailed explanation ( Input/output format, Notes, Images )
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

Sample Input 1:

2
4
1 2 3 4
3
1 5 6

Sample Output 1:

4
2

Explanation of Sample Output 1:

In test case 1,
Given arr = [1, 2, 3, 4]
Longest AP = [1, 2, 3, 4]
So the length of the longest possible AP is 4.

Test Case 2 : 
Given arr = [1, 5, 6]
Longest AP = [1, 5]
So the length of the longest possible AP is 2.

Sample Input 2:

2
4
1 2 10 3
2
1 2

Sample Output 2:

3
2

Explanation of Sample Input 2:

Test Case 1 :  
Given arr = [1, 2, 10, 3]
Longest AP = [1, 2, 3]
So the length of the longest possible AP is 3.

Test Case 2 : 
Given arr = [1, 2]
Longest AP = [1, 2]
So the length of the longest possible AP is 2.
Hint

Can you check all possible common differences that a subsequence can have?.

Approaches (3)
Brute force

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’.
Time Complexity

O(N ^ N), where ‘N’ is the total number of elements in the array.

 

Since we need to check all possible differences and our ‘getAP’ function takes O(N ^ N) time as at each step we are making O(N) recursive calls. Thus the time complexity will be O(N ^ N).

Space Complexity

O(N), where ‘N’ is the total number of elements in the array. 

 

Since our ‘findAP’ function requires O(N) space in the form of recursive stack space. THus the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Longest AP
Full screen
Console