446. Arithmetic Slices II - Subsequence

import java.util.HashMap;

/**
 * Dynamic Programming
 *
 * Refer:
 * https://leetcode.com/problems/arithmetic-slices-ii-subsequence/solution/
 *
 * DP[i][d] denotes the number of weak arithmetic subsequences that ends with
 * A[i] and its common difference is d.
 *
 * Weak arithmetic subsequences are subsequences that consist of at least two
 * elements and if the difference between any two consecutive elements is the
 * same.
 *
 * Assume we want to append a new element A[i] to existing arithmetic
 * subsequences to form new subsequences. We can append A[i] to an existing
 * arithmetic subsequence, only if the difference between the sequence's last
 * element and A[i] is equal to the sequence's common difference.
 *
 * Thus, we can define the state transitions for the element A[i] intuitively:
 * for all j < i, DP[i][A[i] - A[j]] += DP[j][A[i] - A[j]] + 1.
 *
 * The 1 appears here because we can form a new weak arithmetic subsequence for
 * the pair (i, j).
 *
 * DP[j][A[i] - A[j]] represent the number of subsequences that are not weak.
 *
 * Time Complexity: O(N^2)
 *
 * Space Complexity: O(N^2)
 *
 * N = Length of the input array A.
 */
class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        if (A == null || A.length < 3) {
            return 0;
        }

        int result = 0;
        HashMap<Integer, Integer>[] countMap = new HashMap[A.length];

        for (int i = 0; i < A.length; i++) {
            countMap[i] = new HashMap<>();
            for (int j = 0; j < i; j++) {
                // Long is required for overflow. Whenever the difference is beyond the interger
                // range, its ignored.
                long delta = (long) A[i] - A[j];
                if (delta < Integer.MIN_VALUE || delta > Integer.MAX_VALUE) {
                    continue;
                }
                int diff = (int) delta;
                int c1 = countMap[i].getOrDefault(diff, 0);
                int c2 = countMap[j].getOrDefault(diff, 0);
                result += c2;
                countMap[i].put(diff, c1 + c2 + 1);
            }
        }

        return result;
    }
}