Longest Arithmetic Progression [MEDIUM]

Company: Microsoft (2017) , Snapdeal

Question:

Given an array of sorted numbers having no duplicates , write a program to find the length of the LongestArithmetic Progression (LLAP) in it.

Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines.
The first line of each test case contains an integer N , where  N is the size of array.
The second line of each test case contains N space separated integers denoting array input A[i].

Output:
 Print the length of the Longest Arithmetic Progression ​

Constraints:
1 <=T<= 200
1 <= N <= 1000
1 <= arr[i] <= 10000

Example:

Input:
2
6
1  7 10  13  14  19
5
2 4  6 8 10

Output:
4
5

Explanation:
For test case 1:
set[] = {1, 7, 10, 13, 14, 19}
output = 4
The longest arithmetic progression is {1, 7, 13, 19}
For test case 2:
set[] = {2, 4, 6, 8, 10}
output = 5 
The whole set is in AP

Code:

import java.util.Scanner;

public class  LongestArithmeticProgression

{    

    

    public int lap(int[] A)

    {        

        int n = A.length;

        if (n == 1)

        return 1;

        int[][] L = new int[n + 1][n + 1];

        int maxLen = 2;

        for (int j = n - 1; j >= 0; j--)

        {

            int i = j - 1, k = j + 1;

            while (i >= 0 && k < n)

            {

                if (A[i] + A[k] < 2 * A[j])

                    k = k + 1;

                else if (A[i] + A[k] > 2 * A[j])

                {

                    L[i][j] = 2;

                    i = i - 1;

                }

                else 

                {

                    L[i][j] = L[j][k] + 1;

                    maxLen = Math.max(maxLen, L[i][j]);

                    i = i - 1;

                    k = k + 1;

                }

            }

            while (i >= 0)  

            {

                L[i][j] = 2;

                i = i - 1;

            }

        }           

        return maxLen;                    

    }

  

    public static void main(String[] args) 

    {    

        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();

        for(int mi=0;mi<m;mi++){

        int n = sc.nextInt();

        int[] arr = new int[n];

        for (int i = 0; i < n; i++)

            arr[i] = sc.nextInt();

        LongestArithmeticProgression obj = new LongestArithmeticProgression(); 

        int result = obj.lap(arr);       

   System.out.println(result);        

    }

    }

}

Execution Time: 0.15