Longest Arithmetic Sequence ใน C++

คำอธิบายปัญหา

กำหนดอาร์เรย์ A ของจำนวนเต็ม ต้องการหาความยาวของ arithmetic subsequence ที่ยาวที่สุด โดย arithmetic sequence คือลำดับที่ความต่างระหว่างสมาชิกติดกันคงที่

ตัวอย่าง: [9,4,7,2,10] → ผลลัพธ์ 3 (subsequence: [4,7,10] ความต่าง = 3)

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

1. ใช้ dp[i][diff] = ความยาว arithmetic subsequence สูงสุดที่ลงท้ายที่ index i และมีความต่าง diff
2. วน i จาก 0 ถึง n-1, วน j จาก 0 ถึง i-1
3. คำนวณ diff = A[j] - A[i] (หรือ A[i] - A[j] ตามนิยาม)
4. dp[i][diff] = dp[j][diff] + 1 (ถ้ายังไม่มี ให้เริ่มที่ 2)
5. ติดตามค่าสูงสุดตลอดการทำงาน

Complexity: O(n²) เวลา, O(n²) พื้นที่ (ในกรณีแย่ที่สุด)

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        int n = A.size();
        if(n <= 2) return n;
        
        // dp[i] = map
        vector<unordered_map<int, int>> dp(n);
        int ret = 2;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < i; j++) {
                int diff = A[i] - A[j];
                int len = 2;
                if(dp[j].count(diff)) {
                    len = dp[j][diff] + 1;
                }
                dp[i][diff] = max(dp[i][diff], len);
                ret = max(ret, dp[i][diff]);
            }
        }
        return ret;
    }
};

int main() {
    vector<int> v1 = {9,4,7,2,10};
    Solution ob;
    cout << ob.longestArithSeqLength(v1);
    return 0;
}

อินพุต

[9,4,7,2,10]

เอาต์พุต

3