**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);

}

}

## No comments:

Post a Comment