ลำดับเลขคณิตย่อยใน C++ (Arithmetic Slices II - Subsequence)

ภาพรวมปัญหา

ให้อาเรย์ A หาจำนวนลำดับย่อย (subsequence) ที่เป็นลำดับเลขคณิต (arithmetic) และมีความยาวอย่างน้อย 3

ตัวอย่าง

A = [2,4,6,8,10] → Output: 7
ลำดับเลขคณิต: [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]

วิธีแก้ปัญหา: Dynamic Programming

ใช้ dp[i][diff] = จำนวนลำดับเลขคณิตที่จบที่ index i และมีความต่างร่วม = diff

ขั้นตอนหลัก

1. สร้าง unordered_set เก็บค่าทั้งหมดใน A (เพื่อเช็คว่ามีค่าถัดไปหรือไม่)
2. วน i = 1 ถึง n-1, j = i-1 ถึง 0:
   • diff = A[i] - A[j]
   • temp = dp[j][diff] (จำนวนลำดับที่จบที่ j ด้วย diff เดียวกัน)
   • ret += temp (ลำดับเหล่านี้ขยายต่อด้วย A[i] ได้)
   • ถ้า A[i] + diff อยู่ในเซต → dp[i][diff] += temp + 1 (+1 สำหรับคู่ (j,i) เอง)

โค้ด 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));
}

การวิเคราะห์ความซับซ้อน

• เวลา: O(n²) — คู่ (i,j) ทั้งหมด
• พื้นที่: O(n²) — ตาราง dp