Longest Arithmetic Progression

Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such that  A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible. The sequence S1, S2, …, Sk is called an arithmetic progression if Sj+1 – Sj is a constant

solution:
The key is use dynamic programming. We can use the following property here :
If ..., a_{i+1}, a_i, ..., a_3, a_2, a_1, b, c_1, c_2, ..., c_i, c_{i+1}, ... is an A.P., then
a_i + c_i = 2b

Think about how to find a number which is the average of other two numbers in a sorted array
Says pDP[i][j] is the arithmetic progression starting at i and j
for every a, b, c, where b is the average of a and c.
pDP[a][b] = 1 + pDP[b][c]

Algo would be something like :
S = sort(A) .. where A is the given array
Consider each element in S as 'b' (as defined above) and move outward (on both sides) and keep finding all the A.P elements with b as center.
One should be able to create a list 3-tuples and their A.P constants. Then, simply grouping by A.P constants and chaining these 3-tuples in each group should give the chain as well as their lengths. Simply get the one with max length from then on. Time complexity would be O(n^2).

import java.util.Arrays;
import java.util.Comparator;

public class ArthimeticProgression {

	public static void main(String[] args) {
		int a[] = {1,-2,3,5,7,-3,8,11,15,19,-5,22,25,-11};
		PrintLongestProg(a);
	}
	
	public static int FindIndex(RECORD rc[], int n, int index)
	{
		for (int i = 0; i < n; i++)
		{
			if (rc[i].nIndex == index)
				return i;
		}
		return -1;
	}

	public static int PrintLongestProg(int a[])
	{
		int n = a.length;
		if (n <= 1) return n;

		RECORD recs[] = new RECORD[n];
		for (int i = 0; i < n; i++)
		{
			recs[i] = new RECORD();
			recs[i].nVal = a[i];
			recs[i].nIndex = i;
		}

		Arrays.sort(recs, new LessThan());

		int pDP[][] = new int[n][n];

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				pDP[i][j] = 2;

		int nStart = n - 2;
		int nEnd = n - 1;

		for (int i = n - 2; i >= 1; i--)
		{
			int index = FindIndex(recs, n, i);
			if (index < 0) break;

			int l = index - 1;
			int r = index + 1;
			while (l >= 0 && r < n)
			{
				if (recs[l].nVal + recs[r].nVal == 2 * recs[index].nVal)
				{
					if (recs[l].nIndex < i && recs[r].nIndex > i)
					{
						pDP[recs[l].nIndex][i] = pDP[i][recs[r].nIndex] + 1;
						if (pDP[nStart][nEnd] < pDP[recs[l].nIndex][i])
						{
							nStart = recs[l].nIndex;
							nEnd = i;
						}
					}

					l--;
					r++;
				}
				else if (recs[l].nVal + recs[r].nVal < 2 * recs[index].nVal)
					r++;
				else 
					l--;
			}
		}


		int nRet = pDP[nStart][nEnd];
		int nInterval = a[nEnd] - a[nStart];
		System.out.print(a[nStart]+" ");

		while (nEnd < n)
		{
			if (a[nEnd] - a[nStart] == nInterval)
			{
				System.out.print(a[nEnd]+" ");
				nStart = nEnd;
			}

			nEnd++;
		}

		return nRet;
	}
}

class RECORD 
{
	public int nVal;
	public int nIndex;
};

class LessThan implements Comparator<RECORD>
{
	@Override
	public int compare(RECORD r1, RECORD r2) {
		return ((Integer)r1.nVal).compareTo((Integer)r2.nVal);
	}
	
}