Dãy số học dài nhất với chênh lệch cho trước trong C++

Cho mảng arr và số nguyên difference. Tìm độ dài dãy con dài nhất tạo thành cấp số cộng với công sai = difference.

Ví dụ: [1,5,7,8,5,3,4,2,1], difference = -2 → Kết quả: 4 (dãy [7,5,3,1]).

Giải thuật (Động quy hoạch + Hash Map)

1. Map m lưu độ dài dãy con dài nhất kết thúc bằng giá trị x.
2. Duyệt arr: m[x] = 1 + m[x - difference].
3. Cập nhật ans = max(ans, m[x]).
4. Trả về ans.

Ví dụ 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);
    return 0;
}

Đầu vào

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

Đầu ra

4