Các đoạn số học trong C++

Dãy số học là dãy có ít nhất 3 phần tử và hiệu giữa các phần tử liên tiếp bằng nhau. Cho mảng A, đếm số cặp (P, Q) (P < Q) sao cho đoạn A[P..Q] là dãy số học.

Ví dụ: [1,2,3,4] → 3 đoạn: [1,2,3], [2,3,4], [1,2,3,4].

Thuật toán giải quyết (DP tuyến tính)

dp[i] = số đoạn số học kết thúc tại chỉ số i (độ dài ≥ 3).

1. ret = 0, dp[n] = {0}.
2. Với i = 2 .. n-1:
   • Nếu A[i] - A[i-1] == A[i-1] - A[i-2]:
     • dp[i] = 1 + dp[i-1] (mở rộng đoạn cũ + đoạn mới độ dài 3).
     • ret += dp[i].
3. Trả về ret.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int ret = 0, n = A.size();
        vector<int> dp(n, 0);
        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;
    }
};

int main() {
    vector<int> v = {1, 2, 3, 4};
    Solution ob;
    cout << ob.numberOfArithmeticSlices(v);
}

Đầu vào

[1,2,3,4]

Đầu ra

3