C++ 3ms 5 lines DP (runtime O(n), space O(1)) with comments


  • 0

    Idea is standard DP:
    For every element A[i], try to form an arithmetic with A[i] as the ending element in the arithmetic slice.
    If it's successful, we know A[i] has 1 + number of previous longer arithmetics.
    If A[i] can't form an arithmetic as the ending element, there's no other longer arithmetic slice either, and we have zero increment in counter.

    int numberOfArithmeticSlices(vector<int>& A) {
            int cnt = 0;                    // counter for total number of arithmetic slices    
    
            for (int i = 2, lastCnt = 0; i < A.size(); i++) {
                cnt += (A[i] - A[i - 1]) == (A[i - 1] - A[i - 2]) ? ++lastCnt : lastCnt = 0;
            }
            
            return cnt;
    }
    

Log in to reply
 

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