@@ -0,0 +1,2116 @@
+package dynamic_programming.one_d_dp;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.HashMap;%0Aimport java.util.List;%0Aimport java.util.Map;%0A%0Apublic class Q1027LongestArithmeticSequence %7B%0A%0A    //Difficulty: medium%0A    //TAG: dp%0A%0A    /**%0A     * 1027. Longest Arithmetic Sequence%0A     * Given an array A of integers, return the length of the longest arithmetic subsequence in A.%0A     *%0A     * Recall that a subsequence of A is a list A%5Bi_1%5D, A%5Bi_2%5D, ..., A%5Bi_k%5D with 0 %3C= i_1 %3C i_2 %3C ... %3C i_k %3C= A.length - 1, and that a sequence B is arithmetic if B%5Bi+1%5D - B%5Bi%5D are all the same value (for 0 %3C= i %3C B.length - 1).%0A     *%0A     *%0A     *%0A     * Example 1:%0A     *%0A     * Input: %5B3,6,9,12%5D%0A     * Output: 4%0A     * Explanation:%0A     * The whole array is an arithmetic sequence with steps of length = 3.%0A     * Example 2:%0A     *%0A     * Input: %5B9,4,7,2,10%5D%0A     * Output: 3%0A     * Explanation:%0A     * The longest arithmetic subsequence is %5B4,7,10%5D.%0A     * Example 3:%0A     *%0A     * Input: %5B20,1,15,3,10,5,8%5D%0A     * Output: 4%0A     * Explanation:%0A     * The longest arithmetic subsequence is %5B20,15,10,5%5D.%0A     *%0A     *%0A     * Note:%0A     *%0A     * 2 %3C= A.length %3C= 2000%0A     * 0 %3C= A%5Bi%5D %3C= 10000%0A     */%0A%0A    /*%0A    Solution:%0A%0A    DP problem, dp%5Bi%5D is a Map%3CInteger, Integer%3E, which key represent all possible diff between cur - A%5Bpre%5D%0A    value is the max length%0A%0A    every loop keep update global max%0A%0A    Time: O(n%5E2)%0A    Space: O(n)%0A     */%0A%0A    public int longestArithSeqLength(int%5B%5D A) %7B%0A        List%3CMap%3CInteger, Integer%3E%3E list = new ArrayList%3C%3E();%0A        int max = 0;%0A        for (int i = 0; i %3C A.length; i++) %7B%0A            Map%3CInteger, Integer%3E newMap = new HashMap%3C%3E();%0A            list.add(newMap);%0A            for (int j = i - 1; j %3E= 0; j--) %7B%0A                Map%3CInteger, Integer%3E curMap = list.get(j);%0A                int diff = A%5Bi%5D - A%5Bj%5D;%0A                newMap.put(diff,%0A                        Math.max(newMap.getOrDefault(diff, 0),%0A                                curMap.getOrDefault(diff, 1) + 1));%0A                max = Math.max(max, newMap.get(diff));%0A            %7D%0A        %7D%0A        return max;%0A    %7D%0A%0A%7D%0A

1027. Longest Arithmetic Sequence