C++で指定した差分を持つ最長等差部分列を求める方法

問題概要

整数配列 arr と整数 difference が与えられたとき、隣接する要素同士の差がすべて difference と一致するような等差数列をなす最長部分列の長さを求めます。

たとえば、入力が [1,5,7,8,5,3,4,2,1]、difference が -2 の場合を考えてみましょう。このとき最長の等差数列は [7,5,3,1] となるため、答えは 4 になります。

解法のアプローチ

この問題は、連想配列（マップ）を用いた動的計画法によって線形時間で効率的に解くことができます。ポイントは、「その値で終わる等差部分列の最大長」を各要素ごとに記録していくことです。具体的には次の手順で進めます。

• マップ m を定義する（キー：要素の値、値：その値で終わる等差部分列の長さ）
• n を配列 arr のサイズとし、ans を 0 に初期化する
• i を 0 から n−1 までループさせる
  • x := arr[i]
  • m[x] := 1 + m[x − d]（ひとつ前の要素 x − d で終わる部分列に現在の要素をつなげる）
  • ans := max(ans, m[x])
• ans を返す

ある値 x に到達したとき、その直前になりうる値は必ず x − d です。したがって m[x − d] を参照すれば、x で終わる最長の等差部分列の長さが即座に求まります。

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;
    }
};
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

計算量の考察

配列の各要素を一度だけ処理すればよいため、マップ操作を O(1) とみなせば全体の時間計算量は O(n)、空間計算量も O(n) となります。なお、サンプルコードで使っている std::map は平衡二分探索木ベースのため1回の操作が O(log n) かかりますが、std::unordered_map に置き換えれば平均 O(1) となり、より高速に動作します。