package leetcode;

/**
 * https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/
 */
public class Problem1218 {
    public int longestSubsequence(int[] arr, int difference) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem1218 prob = new Problem1218();
        System.out.println(prob.longestSubsequence(new int[]{1,2,3,4}, 1)); // 4
        System.out.println(prob.longestSubsequence(new int[]{1,3,5,7}, 1)); // 1
        System.out.println(prob.longestSubsequence(new int[]{1,5,7,8,5,3,4,2,1}, 2)); // 4
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -256,32 +256,985 @@
     
-// TODO%0A        return 0
+int answer = 0;%0A        HashMap%3CString, Integer%3E memo = new HashMap%3C%3E();%0A        for (int i = 0; i %3C arr.length; i++) %7B%0A            answer = Math.max(answer, longestSubsequence(arr, difference, 0, arr%5Bi%5D, 0, memo));%0A        %7D%0A        return answer;%0A    %7D%0A%0A    private static int longestSubsequence(int%5B%5D arr, int difference, int index, int value,%0A                                          int length, Map%3CString, Integer%3E memo) %7B%0A        if (arr.length == index) %7B%0A            return length;%0A        %7D%0A        String key = index + %22,%22 + value + %22,%22 + length;%0A        if (memo.containsKey(key)) %7B%0A            return memo.get(key);%0A        %7D%0A        int max;%0A        if (arr%5Bindex%5D == value) %7B%0A            max = longestSubsequence(arr, difference, index + 1, arr%5Bindex%5D + difference,%0A                length + 1, memo);%0A        %7D else %7B%0A            max = longestSubsequence(arr, difference, index + 1, value, length, memo);%0A        %7D%0A        memo.put(key, max);%0A        return max
 ;%0A  
@@ -1396,12 +1396,15 @@
 %5D%7B1,
+ 
 2,
+ 
 3,
+ 
 4%7D, 
@@ -1480,12 +1480,15 @@
 %5D%7B1,
+ 
 3,
+ 
 5,
+ 
 7%7D, 
@@ -1564,26 +1564,35 @@
 %5D%7B1,
+ 
 5,
+ 
 7,
+ 
 8,
+ 
 5,
+ 
 3,
+ 
 4,
+ 
 2,
+ 
 1%7D, 
+-
 2));
@@ -1593,20 +1593,366 @@
  -2)); // 4%0A
+        System.out.println(prob.longestSubsequence(new int%5B%5D%7B2, -6, -3, -6, 2, 0%7D, -2)); // 2%0A        System.out.println(prob.longestSubsequence(new int%5B%5D%7B3, 4, -3, -2, -4%7D, -5)); // 2%0A        System.out.println(prob.longestSubsequence(new int%5B%5D%7B3, 1, -2%7D, -5)); // 2%0A        System.out.println(prob.longestSubsequence(new int%5B%5D%7B1, 2%7D, 1)); // 2%0A
     %7D%0A%7D%0A

Update problem 1218