Leetcode 413. Arithmetic Slice 算术序列切片(动态规划，暴力)

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

1, 1, 2, 5, 7

Input: [1, 2, 3, 4]
Output: 3
有三个算术序列切片：
[1,2,3], [2,3,4], [1,2,3,4]
注意，切片是不能跳着选的...

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        if(A.size()<3){
            return 0;
        }
        
        int totalSolution = 0;
        for(int dist=3;dist<=A.size();dist++){
            for(int k=0;k+dist<=A.size();k++){
                // Arithmetic sequence checking for current [k,k+distance] (sub)sequence
                bool isArithmeticSeq = true;
                int diff = A[k+1] - A[k]; 
                for(int p=k+2;p<k+dist;p++){
                    if((A[p]-A[p-1])!=diff){
                        isArithmeticSeq = false;
                        break;
                    }
                }
                if(isArithmeticSeq) totalSolution++;
            
            }
        }
        return totalSolution;
    }
};

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int[] dp = new int[A.length];
        int sum = 0;
        for(int i=2;i<A.length;i++){
            if( (A[i]-A[i-1]) == (A[i-1]-A[i-2]) ){
                dp[i]=dp[i-1]+1;
                sum +=dp[i];
            }else{
                dp[i]=0;
            }
        }
        return sum; 
    }
}