(This question has been seen in the interviews of the following companies: Facebook, Google, Microsoft)
In the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, and 7

Dynamic programming with a map of a map.

public static int llac(int[] array) {
        if(array.length == 0) return 0;
        int max = 1;
        Map> index_to_llac = new HashMap<>(); //Map>
        for(int current = 1; current < array.length; current++) {
            index_to_llac.put(current, new HashMap<>());
            for(int prev = 0; prev < current; prev++) {
                int diff = array[current] - array[prev];
                int length = 2;
                if(index_to_llac.containsKey(prev) && index_to_llac.get(prev).containsKey(diff)) {
                    length = index_to_llac.get(prev).get(diff) + 1;
                }
                Map diff_to_llac = index_to_llac.get(current);
                //if this is a arithmetic progression with [diff] exists before current, add 1 to the length to include current in the progression
                //otherwise, [prev, current] forms a progression of size 2
                diff_to_llac.put(diff, length);
                max = Math.max(length, max);
            }
        }
        return max;
    }