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.

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

Learn from Facebook, Google, Uber senior engineers interviewed 100+ candidates.aonecode.com

Most recent interview questions and system design topics gathered from aonecode alumnus.

One-to-one online classes. Get feedbacks from real interviewers.

Already a coding expert? - Advance straight to hard interview topics of your interest.

New to the ground? - Develop basic coding skills with your own designated mentor.

Days before
interview? - Focus on most important problems in target company question bank.