# 413\. Arithmetic Slices

similiar: https://leetcode.com/problems/arithmetic-slices-ii-subsequence/discuss/1455658/C%2B%2BJavaPython-DP-with-Picture-explained-Clean-and-Concise

similar: https://hackmd.io/@y56/B19p1vYpq [](https://hackmd.io/cIpVDMkFQ7WA5UkwwajoAA?both#873-Length-of-Longest-Fibonacci-Subsequence "873-Length-of-Longest-Fibonacci-Subsequence")873\. Length of Longest Fibonacci Subsequence


class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        def arith(a,b,c): # a,b,c are arithmetic
            return a+c==b*2

        if len(nums)<3: return 0
        
        start=0
        end=None
        tmp=[]
        for i,x in enumerate(nums):
            if i<2: continue
            if arith(nums[i-2],nums[i-1],nums[i]):
                end=i # from start to end, is arith
            else: # fail to be arith, may need to dump the previous result
                if end: # having "end", means we have a good result
                    tmp.append([start,end])
                start=i-1 # the next promising start
                end=None # need to indicate: not yet to be a good result
                
        if end: tmp.append([start,end]) # termination, dump the last good result
        
        ans=0
        for start,end in tmp:
            L=end-start+1
            # 1 +...+ L-2 # all possivle arith series in this start/end
            ans+=(L-2+1)*(L-2)//2
        return ans
            
class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        def arith(a,b,c): # a,b,c are arithmetic
            return a+c==b*2

        if len(nums)<3: return 0
        
        start=0
        tmp=[]
        for i,x in enumerate(nums):
            if i<2: continue
            if arith(nums[i-2],nums[i-1],nums[i]):
                if tmp and tmp[-1][0]==start:
                        tmp[-1][1]=i # extend the "end" of the "start" if keeping arith
                else:
                    tmp.append([start,i])
            else: # fail to be arith, 
                start=i-1 # the next promising start
                
        
        ans=0
        for start,end in tmp:
            L=end-start+1
            # 1 +...+ L-2 # all possivle arith series in this start/end
            ans+=(L-2+1)*(L-2)//2
        return ans
    
class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        if  len(nums) <= 1:
            return 0
        
        diff = []
        for i in range(len(nums) - 1):
            diff.append(nums[i + 1] - nums[i])
            
        pre_diff = None
        count = 0
        diff_continuous_count = []
        for d in diff:
            if d is None or d == pre_diff:
                count += 1
            else:
                pre_diff = d
                diff_continuous_count.append(count)
                count = 1
        diff_continuous_count.append(count)
        
        ans = 0
        for diff_count in diff_continuous_count:
            if diff_count > 1:
                num_count = diff_count + 1
                # 1 + ... + (num_count - 3 + 1) 
                ans += ((num_count - 3 + 1) + 1) * (num_count - 3 + 1) // 2
        return ans

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

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

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