C++-এ অ্যারিথমেটিক স্লাইস

অ্যারিথমেটিক সিকোয়েন্স = কমপক্ষে ৩ উপাদান এবং প্রতিটি আডজেসেন্ট পার্থক্য সমান। অ্যারে A-তে কতটি অ্যারিথমেটিক স্লাইস (P,Q) আছে তা বের করতে হবে।

উদাহরণ: [1,2,3,4] → ৩ ([1,2,3], [2,3,4], [1,2,3,4])।

সমাধানের ধাপসমূহ

• DP: dp[i] = i-তম ইনডেক্সে শেষ হওয়া অ্যারিথমেটিক স্লাইসের সংখ্যা।
• যদি A[i]-A[i-1] == A[i-1]-A[i-2] হয়, dp[i] = 1 + dp[i-1]।
• উত্তর = সব dp[i] এর যোগফল।

C++ উদাহরণ

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

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

ইনপুট

[1,2,3,4]

আউটপুট

3