O(n^2) Time, but Very Easy to Understand


  • 1
    C

    dp[i] means the number of arithmetic slices in current sequence ending with A[i]

    Absolutely, It can be optimized to O(1) space complexity.

    int numberOfArithmeticSlicesFirst(vector<int>& A)
    {
        int n = A.size();
        if(n < 3) return 0;
        
        vector<int> dp(n, 0);
        for(int i = 2; i < n; ++i)
        {
            dp[i] = dp[i-1];
            for(int k = i; k >= 2; --k)
            {
                if(A[k-2] - A[k-1] != A[k-1] - A[k])
                    break;
                ++dp[i];
            }
        }
        
        return dp[n-1];
    }
    

Log in to reply
 

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