Length of longest AP sequence

Length of longest AP sequence

  June 17, 2018    

---

We are given an sorted array , now we need to find longest subseqence forming A.P.
Idea is to look for every gap but it will take more time to perform that.

So we are going to fix middle element and find two element such that these 3 elements  form A.P.
This find can be done using sliding window concept
and if any sequence found then we can say that from start to fix subseqence AP=fix to k subsequence AP+1.

Base case:
if elements are >=2 then ap will be atleast of 2 size.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class longestAP
 {
  public static int fn(int a[],int n)
  {
    if(n<=2) return n;
    int dp[][]=new int[n][n];
    int res=2;
    for (int i = 0; i < n; i++)
           dp[i][n - 1] = 2;
   //fixing jth pointer and looking both side for AP pair having a[i]+a[k]==2*a[j]
    for(int j=n-2;j>=1;--j)
    {
      int i=j-1,k=j+1;
      while(i>=0 && k<n)
      {
        if(a[i]+a[k]==2*a[j])
        {
          dp[i][j]=dp[j][k]+1;
          res=Math.max(res,dp[i][j]);
          --i;
          ++k;
        }
        else
        {
         dp[i][j]=Math.max(dp[i][j],2);
          if(a[i]+a[k]<2*a[j])
          ++k;
          else
          --i;
        }
      }
      while (i >= 0)
           {
               dp[i][j] = 2;
               i--;
           }
    }
    return res;
  }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int arr[]=new int[n];
    for(int i=0;i<n;++i)
    arr[i]=ab.nextInt();
    System.out.println(fn(arr,n));
}
}
}

Time : O(n^2)