Longest Arithmetic Progression

Problem: 

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

The solution is to that using difference between two numbers in the list as key to store the maximum length for each difference. If the difference is already met before, then we can skip it.

Complexity: O(n^2) since there is n*(n-1) differences between the numbers in a list

public static List<Integer> findMaxArithmeticsSeq(int[] num){

int maxL = 0;

List<Integer> result = new ArrayList<Integer>();

//the difference between two numbers in the list defines the maxL of the sequence

//store the mapping will help to reduce the number of the iterations

Map<Integer, Integer> diff2Length = new HashMap<Integer, Integer>();

for(int i=0; i<num.length-1; i++){

for(int j=i+1; j<num.length; j++){

int diff = num[j]-num[i];

//we don't need to continue since max Length for this difference is already found

if(diff2Length.containsKey(diff))

continue;

List<Integer> found = new ArrayList<Integer>();

found.add(num[i]);

int pre = num[i];

for(int k=j; k<num.length; k++){

if(num[k] - pre == diff){

found.add(num[k]);

pre = num[k];

}

}

diff2Length.put(diff, found.size());

if(found.size() > maxL){

maxL = found.size();

result = found;

}

}

}

return result;

}