package leetcode;

/**
 * https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/
 */
public class Problem1218 {
    public int longestSubsequence(int[] arr, int difference) {
        int answer = 0;
        Integer[][] memo = new Integer[arr.length][arr.length];
        for (int i = 0; i < arr.length; i++) {
            answer = Math.max(answer, longestSubsequence(arr, difference, i, i + 1, memo) + 1);
        }
        return answer;
    }

    private static int longestSubsequence(int[] arr,
                                          int difference,
                                          int previousIndex,
                                          int currentIndex,
                                          Integer[][] memo) {
        if (arr.length == currentIndex) {
            return 0;
        }
        if (memo[previousIndex][currentIndex] != null) {
            return memo[previousIndex][currentIndex];
        }
        int max;
        if (arr[currentIndex] == arr[previousIndex] + difference) {
            max = longestSubsequence(arr, difference, currentIndex, currentIndex + 1, memo) + 1;
        } else {
            max = longestSubsequence(arr, difference, previousIndex, currentIndex + 1, memo);
        }
        memo[previousIndex][currentIndex] = max;
        return max;
    }

    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
        System.out.println(prob.longestSubsequence(new int[]{2, -6, -3, -6, 2, 0}, -2)); // 2
        System.out.println(prob.longestSubsequence(new int[]{3, 4, -3, -2, -4}, -5)); // 2
        System.out.println(prob.longestSubsequence(new int[]{3, 1, -2}, -5)); // 2
        System.out.println(prob.longestSubsequence(new int[]{1, 2}, 1)); // 2
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -280,62 +280,50 @@
     
+Map%3C
 Integer
-%5B%5D%5B%5D memo = new Integer%5Barr.length%5D%5Barr.length%5D
+, Integer%3E dp = new HashMap%3C%3E()
 ;%0A  
@@ -383,691 +383,42 @@
     
-answer = Math.max(answer, longestSubsequence(arr, difference, i, i + 1, memo) + 1);%0A        %7D%0A        return answer;%0A    %7D%0A%0A    private static int longestSubsequence(int%5B%5D arr,%0A                                          int difference,%0A                                          int previousIndex,%0A                                          int currentIndex,%0A                                          Integer%5B%5D%5B%5D memo) %7B%0A        if (arr.length == currentIndex) %7B%0A            return 0;%0A        %7D%0A        if (memo%5BpreviousIndex%5D%5BcurrentIndex%5D != null) %7B%0A            return memo%5BpreviousIndex%5D%5BcurrentIndex%5D;%0A        %7D%0A        int max;%0A        if (arr%5BcurrentIndex%5D == arr%5BpreviousIndex%5D +
+int val = dp.getOrDefault(arr%5Bi%5D -
  dif
@@ -428,1010 +428,127 @@
 ence
-) %7B%0A            max = longestSubsequence(arr, difference, currentIndex, currentIndex + 1, memo) + 1;%0A        %7D else %7B%0A            max = longestSubsequence(arr, difference, previousIndex, currentIndex + 1, memo);%0A        %7D%0A        memo%5BpreviousIndex%5D%5BcurrentIndex%5D = max;%0A        return max;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1218 prob = new Problem1218();%0A        System.out.println(prob.longestSubsequence(new int%5B%5D%7B1, 2, 3, 4%7D, 1)); // 4%0A        System.out.println(prob.longestSubsequence(new int%5B%5D%7B1, 3, 5, 7%7D, 1)); // 1%0A        System.out.println(prob.longestSubsequence(new int%5B%5D%7B1, 5, 7, 8, 5, 3, 4, 2, 1%7D, -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
+, 0) + 1;%0A            answer = Math.max(answer, val);%0A            dp.put(arr%5Bi%5D, val);%0A        %7D%0A        return answer;
 %0A   

Solve problem 1218