C++-এ আритমেটিক স্লাইস II - সাবসিকোয়েন্স

আরিথমেটিক সাবসিকোয়েন্স গণনা

একটি অ্যারে A দেওয়া আছে। একটি সাবসিকোয়েন্স স্লাইস হলো সূচক들의 সিকোয়েন্স (K0, K1, ..., Kn) যেখানে 0 ≤ K0 < K1 < ... < Kn < N। এটি আরিথমেটিক স্লাইস হবে যদি A[K0], A[K1], ..., A[Kn] একটি আরিথমেটিক সিকোয়েন্স তৈরি করে (অর্থাৎ n ≥ 2)। আমাদের কাজ হল таких সাবসিকোয়েন্সের মোট সংখ্যা গণনা করা।

উদাহরণ: [2,4,6,8,10] এর জন্য উত্তর ৭। স্লাইসগুলো: [2,4,6], [2,4,10], [4,6,8], [6,8,10], [2,4,6,8], [4,6,8,10], [2,4,6,8,10]

সমাধানের পদ্ধতি (ডাইনামিক প্রোগ্রামিং)

• ret := 0
• একটি নেস্টেড ম্যাপ dp ব্যবহার করুন: dp[i][diff] = সূচক i-তে শেষ হওয়া এবং পার্থক্য diff वाले আরিথমেটিক সাবসিকোয়েন্সের সংখ্যা (দৈর্ঘ্য ≥ 2)
• একটি সেট s ব্যবহার করুন অ্যারের সব উপাদান রাখার জন্য
• দ্বৈত লুপ i = 1..n-1, j = i-1..0:
  • diff := A[i] - A[j]
  • ওভারফ্লো চেক করুন
  • temp := dp[j][diff] (ডিফল্ট ০)
  • ret += temp
  • যদি A[i] + diff সেট s-তে থাকে, তবে dp[i][diff] += temp + 1
• ret ফেরত দিন

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int ret = 0;
        unordered_map<lli, unordered_map<lli, lli>> dp;
        unordered_set<int> s(A.begin(), A.end());
        int n = A.size();
        for(int i = 1; i < n; i++) {
            for(int j = i - 1; j >= 0; j--) {
                lli diff = (lli)A[i] - (lli)A[j];
                if(diff <= INT_MIN || diff > INT_MAX) continue;
                int temp = dp[j].count(diff) ? dp[j][diff] : 0;
                ret += temp;
                if(s.count(A[i] + diff)) dp[i][diff] += temp + 1;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2,4,6,8,10};
    cout << (ob.numberOfArithmeticSlices(v));
    return 0;
}

ইনপুট

{2,4,6,8,10}

আউটপুট

7