Arithmetic Slices: From Slow to Fast Solutions

First Solution: 2D DP

Check all slices with length greater than 3. This method runs slow.

Better Solution: 1D DP

dp[i] represents the count of arithmetic slices ending at A[i]. When we add a new number to existing arithmetic slices, we get one more arithmetic slice or none at all.

int numberOfArithmeticSlices(vector<int>& A) {
    int len=A.size();
    vector<int> dp(A.size(), 0);
    int res=0;
    if (len>=3 && A[2]-A[1]==A[1]-A[0]) {
        dp[2]=1;
        res+=dp[2];
    }
    for(int i=3;i<len;++i) {
        if (A[i]-A[i-1]==A[i-1]-A[i-2]) {
            dp[i]=dp[i-1]+1;
        }
        res+=dp[i];
    }
    return res;
}

#DP

Adding Integers Without Plus or Minus Balanced Binary Tree