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;
    }
}

results matching ""

    No results matching ""