New update is available. Click here to update.

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