Longest Arithmetic Progression

Find longest Arithmetic Progression in an integer array A of size N, and return its length.

More formally, find longest sequence of indices, 0 < i1 < i2 < … < ik < ArraySize(0-indexed) such that sequence A[i1], A[i2], …, A[ik] is an Arithmetic Progression.

Arithmetic Progression is a sequence in which all the differences between consecutive pairs are the same, i.e sequence B[0], B[1], B[2], …, B[m - 1] of length m is an Arithmetic Progression if and only if B[1] - B[0] == B[2] - B[1] == B[3] - B[2] == … == B[m - 1] - B[m - 2]

Note: The common difference can be positive, negative or 0.

The first and the only argument of input contains an integer array, A.

Return an integer, representing the length of the longest possible arithmetic progression.

1 <= N <= 1000
1 <= A[i] <= 1e9

Input 1:
    A = [3, 6, 9, 12]

Output 1:
    4

Explanation 1:
    [3, 6, 9, 12] form an arithmetic progression.

Input 2:
    A = [9, 4, 7, 2, 10]

Output 2:
    3

Explanation 2:
    [4, 7, 10] form an arithmetic progression.

Solution:

Time: O(n)
Space: O(n^2)

public class Solution {
    // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
    public int solve(final int[] A) {
        int n = A.length;
        // dp[i] = longest length of arithmetic progression ending at i
        // diff[i] = diff that provides max length of progression ending at i
        // dp[i] = max(dp[i], 1 + dp[j] if diff[j] = A[i] - A[j])
        // max(dp[n])
        if (n <= 2) return n;
        int[] dp = new int[n];
        Set<Integer>[] diff = new HashSet[n];
        int max = 1;
        dp[0] = 1;
        dp[1] = 2;
        diff[0] = new HashSet<>(Arrays.asList(A[0]));
        diff[1] = new HashSet<>(Arrays.asList(A[1] - A[0]));
        for (int i = 2; i < n; i ++) {
            dp[i] = 2;
            for (int j = 0; j < i; j ++) {
                if (diff[i] == null) {
                    diff[i] = new HashSet<>(Arrays.asList(A[i] - A[j]));
                }
                if (diff[j].contains(A[i] - A[j])) {
                    if (dp[j] >= dp[i]) {
                        dp[i] = 1 + dp[j];
                        diff[i] = diff[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        diff[i].add(A[i] - A[j]);
                    }
                } else if (dp[i] == 2) {
                    diff[i].add(A[i] - A[j]);
                }
            }
            max = Math.max(max, dp[i]);
        }
        // System.out.println(Arrays.toString(dp));
        // System.out.println(Arrays.toString(diff));
        return max;
    }
}