ลำดับเลขคณิตยาวที่สุดที่มีความต่างกำหนดใน C++

สมมติว่าเรามีอาร์เรย์จำนวนเต็ม arr และจำนวนเต็ม difference ต้องหาความยาวของ subsequence ยาวที่สุดที่เป็นลำดับเลขคณิตและมีความต่างระหว่างสมาชิกติดกันเท่ากับ difference

ตัวอย่าง: [1,5,7,8,5,3,4,2,1], difference = -2 ผลลัพธ์: 4 เพราะลำดับยาวที่สุดคือ [7,5,3,1]

ขั้นตอนการแก้ปัญหา (DP + Hash Map)

• กำหนดแผนที่ m เก็บความยาว subsequence สุดท้ายที่ลงท้ายด้วยค่า x
• n := ขนาดของ arr, ans := 0
• วนลูป i จาก 0 ถึง n-1:
  • x := arr[i]
  • m[x] := 1 + m[x - difference]
  • ans := max(ans, m[x])
• คืนค่า ans

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

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

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int d) {
        int n = arr.size();
        map <int,int> m;
        int ans = 0;
        for(int i = 0; i < n; i++) {
            int x = arr[i];
            m[x] = 1 + m[x - d];
            ans = max(ans, m[x]);
        }
        return ans;
    }
};

int main() {
    vector<int> v1 = {1,5,7,8,5,3,4,2,1};
    Solution ob;
    cout << ob.longestSubsequence(v1, -2);
}

อินพุต

[1,5,7,8,5,3,4,2,1] -2

เอาต์พุต

4