Longest Arithmetic Progression
http://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/
public class Solution {
// DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
public int solve(final int[] A) {
if(A == null || A.length == 0){
return 0;
}
int n = A.length;
if(n <= 2){
return 2;
}
int[][] dp = new int[n][n];
for(int i = 0; i < n - 1; i++){
dp[i][n - 1] = 2;
}
int max = 2;
for(int j = n - 2; j >= 1; j--){
int i = j - 1, k = j + 1;
while(i >= 0 && k < n){
if(A[i] + A[k] == 2 * A[j]){
dp[i][j] = dp[j][k] + 1;
max = Math.max(max, dp[i][j]);
i--;
k++;
}else if(A[i] + A[k] < 2 * A[j]){
k++;
}else{
dp[i][j] = 2;
i--;
}
}
while(i >= 0){
dp[i][j] = 2;
i--;
}
}
return max;
}
}