Interviews

Longest Arithmetic Progression

user profile image
System made a post.
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;
    }



One-on-One Algorithm and Coding Training

One-on-One System Design Training

One-on-One Mock Interview

Get one-to-one training from Google Facebook engineers


Top-notch Professionals

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.


Customized Private Class

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.


Free Consultation

aonecoding@gmail.com