Longest Arithmetic Progression

题目地址：
http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/

题目：

Given a set of numbers, find the Length of the Longest Arithmetic Progression (LLAP) in it.

Examples:

set[] = {1, 7, 10, 15, 27, 29}
output = 3
The longest arithmetic progression is {1, 15, 29}

set[] = {5, 10, 15, 20, 25, 30}
output = 6
The whole set is in AP

解题思路：
https://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_22_-_Longest_arithmetic_progression.jsp

http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/

代码：

public class LongestArithmeticProgression {
    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
            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]);
                    k++;
                    i--;
                }
            }
        }
        System.out.println (maxAP);
    }
}