Arithmetic Slices trong C ++

Giả sử chúng ta có một dãy số được gọi là cấp số cộng nếu nó gồm ít nhất ba phần tử và nếu hiệu của hai phần tử liên tiếp bất kỳ là như nhau. Vì vậy, ví dụ, đây là dãy số học:[1, 3, 5, 7, 9], [7, 7, 7, 7], [3, -1, -5, -9], Nhưng dãy sau thì không Môn số học. [1, 1, 2, 5, 7]

Bây giờ, một mảng A được lập chỉ mục bằng 0 gồm N số được đưa ra. Một lát cắt của mảng đã cho đó là bất kỳ cặp số nguyên nào (P, Q) sao cho 0 <=P

Vì vậy, nếu đầu vào là [1,2,3,4], thì đầu ra sẽ là 3, vì các phần tử là [1,2,3], [2,3,4] và [1,2,3, 4]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0, n:=kích thước của A, tạo một mảng dp có kích thước n
• cho tôi trong phạm vi từ 2 đến n - 1
  • nếu a [i] - a [i - 1] =a [i - 1] - a [i - 2], thì
    • dp [i]:=1 + dp [i - 1]
    • tăng số lượt truy cập lên dp [i]
• trả lời lại

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
      int numberOfArithmeticSlices(vector<int>& A) {
         int ret = 0;
         int n = A.size();
         vector <int> dp(n);
         for(int i = 2; i < n; i++){
            if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]){
               dp[i] = 1 + dp[i - 1];
               ret += dp[i];
            }
         }
         return ret;
      }  
};
main(){
   vector<int> v = {1,2,3,4};
   Solution ob;
   cout << (ob.numberOfArithmeticSlices(v));
}

Đầu vào

[1,2,3,4]

Đầu ra

3