Make delicious recipes!

Longest arithmetic progression in a sorted array



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
  1.    arr[i] + arr[k] = 2*arr[j] and
  2.    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();
        }
    }
}
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2

Checking out 8
    Found 7, 8, 9
    lookup[4][5] = lookup[5][6] (2) + 1
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  0  3  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2

Checking out 7
    Found 5, 7, 9
    lookup[3][4] = lookup[4][6] (2) + 1
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  3  0  2
  0  0  0  0  0  3  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2

Checking out 5
    Found 3, 5, 7
    lookup[1][3] = lookup[3][4] (3) + 1
    Found 1, 5, 9
    lookup[0][3] = lookup[3][6] (2) + 1
  0  0  0  3  0  0  2
  0  0  0  4  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  3  0  2
  0  0  0  0  0  3  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2

Checking out 4
    Found 3, 4, 5
    lookup[1][2] = lookup[2][3] (0) + 1
    Found 1, 4, 7
    lookup[0][2] = lookup[2][4] (0) + 1
  0  0  1  3  0  0  2
  0  0  1  4  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  3  0  2
  0  0  0  0  0  3  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2

Checking out 3
    Found 1, 3, 5
    lookup[0][1] = lookup[1][3] (4) + 1
  0  5  1  3  0  0  2
  0  0  1  4  0  0  2
  0  0  0  0  0  0  2
  0  0  0  0  3  0  2
  0  0  0  0  0  3  2
  0  0  0  0  0  0  2
  0  0  0  0  0  0  2

Max AP length = 5
1, 3, 5, 7, 9, 


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, 






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal