数列 \(A\) の要素 \(A_i\) を\(i=1,2,\ldots,M\) の順番に決め打っていく時、次決める要素に関係がある要素はその直前決め打った要素のみです。その性質を使い、以下のような動的計画法を考えます。

\(dp[i][j] =\) \((A_1,\ldots,A_i)\)まで決め打って、\(A_i=S_j \)であるような数列 \(A\) のうち \(D_k=|A_k-A_{k+1}|\) を満たす \(1\) 以上 \(i-1\) 以下の整数 \(k\) の個数として考えられる最大値

この時、この問題の答えは \(dp[N][1],dp[N][2],\ldots ,dp[N][M]\) の最大値です。

このDPは 初期条件 \(dp[1][1]=0,dp[1][2]=0,\ldots,dp[1][M]=0\) として、\(dp[i]\) は \(dp[1],dp[2],\ldots,dp[i-1]\) の結果から以下の式で計算できます

\(\displaystyle dp[i][j]=\max (\max_{\substack{1 \leq k \leq M \\ |S_k-S_j| \neq D_{i-1}}}dp[i-1][k],\max_{\substack{1 \leq k \leq M \\ |S_k-S_j| = D_{i-1}}}dp[i-1][k] +1) \)

よって、各 \(i,j,k\) 全ての値を取って動的計画法を計算することができます。しかし、この時計算量は \(O(N M^2)\) になり、実行時間制限に間に合いません。

しかし、先ほどの遷移の左の項の \(k\) は \(1 \leq k \leq M\) を満たす全ての整数としてもこの式は正しいです。 つまり、\(dp[i-1]\) の最大値と、\(|S_j-S_k|=D_{i-1}\) を満たすような \(k\) を各 \(i,j\) に対して求められれば良いです。\(S\) は相異なるため、\(|S_j-S_k|=D_{i-1}\) を満たす \(k\) は高々 \(2\) 個です。具体的にその \(k\) を求めるには、連想配列などを用いて\(X\) が与えられた時、 \(S_i=X\) を満たす \(i\) がすぐ求めることができます。

よって、この動的計画法を \(O(NM)\) または \(O(NM\log M)\) で解くことができます。

実装例 (C++):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> s(n);
    for (auto &e : s)
        cin >> e;
    vector<int> d(m - 1);
    for (auto &e : d)
        cin >> e;
    vector<int> dp(n, 0);
    unordered_map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        mp[s[i]] = i;
    }
    for (int i = 0; i < m - 1; ++i) {
        const int ma = *max_element(dp.begin(), dp.end());
        vector<int> ndp(n, ma);
        for (int j = 0; j < n; ++j) {
            if (mp.count(s[j] + d[i])) {
                ndp[mp[s[j] + d[i]]] = max(ndp[mp[s[j] + d[i]]], dp[j] + 1);
            }
            if (mp.count(s[j] - d[i])) {
                ndp[mp[s[j] - d[i]]] = max(ndp[mp[s[j] - d[i]]], dp[j] + 1);
            }
        }
        dp = move(ndp);
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
}