Dynamic Programming, Java Solution with detailed explanation!


  • 3
    L

    Given an array a1, a2, ..., ai, ..., an
    T(i,d) is the number of arithmetic subsequence with difference d that ends at ai

    Thus, we have T(i,d) = sum(T(j,d) + 1) for all thej < iand ai - aj = d
    T(0, d) == 0

    Consider the range of d could be from[Integer.MIN_VALUE, INTEGER.MAX_VALUE], it would be too space-consuming to initialize such 2-d array. However, we can combine the 1-d array with the hashmap to create a new dynamic 2-d array.

    In general, for this definition, it assumes that the length of subseqeunce can be>= 2. However, according to the question, we only count subsequence of which the length is>= 3. For example, given array [1, 2, 3] , 1, 2 is also considered to be a legal arithmetic sequence, but what we need to is just 1, 2, 3.

    And it is hard to adjust the definition above, because we need to know the length of subsequence, but the above definition does not provide this information. So we can only filter the 2 length subsequence in the code. Moreover, in the code below, we can only count the sequence of which the length is at least 4, 5, or more based on the requirement of problem.

    Special thanks to fun4LeetCode.

    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            if (A == null || A.length == 0) return 0;
            
            Map<Integer, Integer>[] map = new Map[A.length];         // dynamic 2-d array
            // <d, #>
            int res = 0;
            
            for (int i = 0; i < A.length; i++) {
                map[i] = new HashMap<>();
                for (int j = 0; j < i; j++) {
                    long diff = (long)A[i] - A[j];
                    if (diff > Integer.MAX_VALUE || diff < Integer.MIN_VALUE) continue;
                    int d = (int) diff;
                    int T_jd = map[j].getOrDefault(d, 0);
                    int increase = T_jd + 1;            // the amount of increase for each time
                    
                    /* This statement is used to adjust the acceptable subsequnce based on the requirement of problem
                       If the minimum length of subsequence should be 3, then res += increase > 1? (increase-1) : 0; Or simply res += increase-1;
                       If the minimum length of subsequence should be 4, then res += increase > 2? (increase-2) : 0;
                       If the minimum length of subsequence should be 5, then res += increase > 3? (increase-3) : 0;
                       ...
                       ...
                       ...
                     */
                    res += increase > 1? (increase-1) : 0;  //filter
                    map[i].put(d, map[i].getOrDefault(d, 0) + increase);
                }
            }
            return res;
            
            
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.