1027. Longest Arithmetic Sequence

We use a map array differToNum to record the longest sequence. Each Entry in differToNum[i] records the longest sequence (Entry.getValue()) at difference Entry.getKey() which ends at A[i]. For example, if A = [3 6 9 12], then differToNum = [ {}, {<3, 2>}, {<6, 2>, <3, 3>}, {<9, 2>, <6, 2>, <3, 4>} ].

public int longestArithSeqLength(int[] A) {
    int max = 0;
    Map<Integer, Integer> differToNum[] = new Map[A.length];
    for(int i = 0; i < A.length; i++)
	differToNum[i] = new HashMap<Integer, Integer>();
    for(int i = 1; i < A.length; i++) {
	for(int j = 0; j < i; j++) {
	    int prev = differToNum[j].getOrDefault(A[i] - A[j], 1);
	    differToNum[i].put(A[i] - A[j], prev + 1);
	    max = Math.max(prev + 1, max);
        }
    }
    return max;
}