Problem: Given a sorted array, find the longest arithmetic progression in the same.
Solution: Before solving this problem, let us solve a different problem first.
How to find if a sorted array contains an arithmetic progression of length 3?
This can be done by looping over the array and then finding numbers 'i' and 'k' on either side of current number 'j' such that
arr[i] + arr[k] = 2*arr[j] and
i < j < k
The above algorithm is n*(n + log(n)) = O(n2) and can be extended to find largest AP in a sorted array as follows:
Create a table 'lookup' such that lookup[j][k] will give the length of the longest AP whose first two
elements are arr[j] and arr[k].
Then every time another element 'i' is found in the same series, we can updated the lookup as:
lookup[i][j] = lookup[j][k] + 1;
Code:
Java Code
Sample Execution
public class LongestAP
{
public static void main(String[] args)
{
int sortedArr [] = new int [] {1, 3, 4, 5, 7, 8, 9};
int n = sortedArr.length;
int lookup[][] = new int [n][n];
int maxAP = 2;
// Any 2-letter series is an AP
// Here we initialize only for the last column of lookup because
// all i and (n-1) pairs form an AP of size 2
for (int i=0; i<n; i++)
lookup[i][n-1] = 2;
// Loop over the array and find two elements 'i' and 'k' such that i+k = 2*j
for (int j=n-2; j>=1; j--)
{
int i = j-1; // choose i to the left of j
int k = j+1; // choose k to the right of j
printLookup(lookup);
System.out.println ("\nChecking out " + sortedArr[j]);
while (i >= 0 && k <= n-1)
{
int isAP = ( sortedArr[i] + sortedArr[k] ) - 2*sortedArr[j];
if (isAP < 0)
{
k++;
}
else if (isAP > 0)
{
i--;
}
else
{
debugState(sortedArr, lookup, j, i, k);
lookup[i][j] = lookup[j][k] + 1;
maxAP = Math.max(maxAP, lookup[i][j]);
k++;
i--;
}
}
}
System.out.println (maxAP);
}
private static void debugState(int[] sortedArr, int[][] lookup, int j, int i, int k)
{
System.out.println(" Found " + sortedArr[i] + ", " +
sortedArr[j] + ", " +
sortedArr[k]);
System.out.println(" lookup["+i+"]["+j+"] = lookup["+j+"]["+k+"] ("
+ lookup[j][k] + ") + 1");
}
static void printLookup(int[][] lookup)
{
for (int i=0; i<lookup.length; i++)
{
for (int j=0; j<lookup[i].length; j++)
{
System.out.print (String.format("%3d", lookup[i][j]));
}
System.out.println();
}
}
}
It is easy to print the AP itself as follows:
(Just add the code as shown in line 44 to 50 and then from 59 to 64)
public class LongestAP
{
public static void main(String[] args)
{
int sortedArr [] = new int [] {3, 4, 5, 7, 8, 9, 11, 13, 14, 15, 16, 17, 18};
int n = sortedArr.length;
int lookup[][] = new int [n][n];
int maxAP = 2;
int apTerm = 0;
int apStart = 0;
// Any 2-letter series is an AP
// Here we initialize only for the last column of lookup
for (int i=0; i<n; i++)
lookup[i][n-1] = 2;
// Loop over the array and find two elements 'i' and 'k' such that i+k = 2*j
for (int j=n-2; j>=1; j--)
{
int i = j-1; // choose i to the left of j
int k = j+1; // choose k to the right of j
while (i >= 0 && k <= n-1)
{
int isAP = ( sortedArr[i] + sortedArr[k] ) - 2*sortedArr[j];
if (isAP < 0)
{
k++;
}
else if (isAP > 0)
{
i--;
}
else
{
lookup[i][j] = lookup[j][k] + 1;
maxAP = Math.max(maxAP, lookup[i][j]);
if (maxAP == lookup[i][j])
{
// Store the Arithmetic Progression's term
// And the start point of the AP
apTerm = sortedArr[j] - sortedArr[i];
apStart = i;
}
k++;
i--;
}
}
}
System.out.print("Max AP length = " + maxAP + "\n" + sortedArr[apStart] + ", ");
for (int i=apStart+1; i<n; i++)
{
if ((sortedArr[i] - sortedArr[apStart])%apTerm == 0)
System.out.print(sortedArr[i] + ", ");
}
}
}
Sample Execution:
Max AP length = 6
3, 5, 7, 9, 11, 13, 15, 17,
Got a thought to share or found a bug in the code? We'd love to hear from you:
