Plain Vanilla java DP solution: probably easier to understand than others


  • 0
    A

    This solution has the benefit that it can be easily extended to calculate all possible arithmetic slides (not necessarily one by one close to each others), for example:

    Given array [1,2,3,4,5], if "[1,3,5]" is also counted, the following code can be adapted to accommodate that by looping through 'secondIndex'

    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            // algorithm: dynamic programming; assume we have the results for the previous (n-1) numbers
            //  now with the new number, check how many new arithmetic slices ended with the last number
            if (null == A || 2 >= A.length) {
                return 0;
            }
            int[] results = new int[A.length];
            // this array records the number of arithmetic slice ENDED WITH IT
            results[0] = 0;
            results[1] = 0;
            for (int firstIndex = 0; firstIndex < A.length - 2; firstIndex++) {
                int firstNum = A[firstIndex];
                int secondIndex = firstIndex + 1;
    
                int secondNum = A[secondIndex];
                // check arithmetic sequence
                int numDelta = secondNum - firstNum;
    
                int nextIndex = secondIndex + 1;
                int nextNum = secondNum + numDelta;
                while (nextIndex < A.length) {
                    // find an arithmetic sequence
                    if (A[nextIndex] == nextNum) {
                        results[nextIndex] ++;
                    } else {
                        // make sure we break here -- do NOT check subsequent numbers!
                        break;
                    }
                    // proceed
                    nextIndex ++;
                    nextNum += numDelta;
                }
            }
    
            // now count the total number of arithmetic slices
            int count = 0;
            for (int index = 0; index < A.length; index++) {
                count += results[index];
            }
            return count;
        }
    }

Log in to reply
 

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