隣接する要素の差が0または1となる最長部分列の求め方 | C++実装解説

問題の概要

任意のサイズの整数配列が与えられたとき、「隣接する要素同士の差が0または1」という条件を満たす部分列(サブシーケンス)の中で、最も長いものの長さを求めるのがこの問題の目的です。

素朴にすべての部分列を調べると膨大な時間がかかってしまいますが、unordered_map(ハッシュマップ)を活用すれば、配列を一度走査するだけで O(n) の線形時間で答えを導き出せます。

入出力の例

例1

入力 − int arr[] = { 2, 1, 7, 6, 5 }

出力 − 隣接要素の差が0または1となる最長部分列の長さ: 3

説明 − 条件を満たす部分列には {7, 6, 5}(差はいずれも1)や {2, 1}(差は1)があります。この中で最も長いのは {7, 6, 5} のため、答えは 3 になります。

例2

入力 − int arr[] = { 2, 3, 1, 7, 5, 6, 7, 8 }

出力 − 隣接要素の差が0または1となる最長部分列の長さ: 4

説明 − 部分列 {5, 6, 7, 8} は隣接要素の差がすべて1であり、これより長い条件を満たす部分列は存在しないため、答えは 4 になります。

アルゴリズムの考え方

このアルゴリズムでは、ハッシュマップの「キー」に要素の値を、「値」にその値を末尾とする部分列の最大長を記録していきます。新しい要素を処理する際には、自分の値から ±1 以内(つまり arr[i]-1、arr[i]、arr[i]+1)のキーがマップに登録済みかどうかを確認し、その中で最も長いものに1を加えた値を現在の要素の長さとします。

具体的な手順は以下の通りです。

• 正の要素も負の要素も含み得る整数型の配列を受け取ります。
• 配列のサイズを計算し、配列とサイズを関数に渡して以降の処理を行います。
• 一時変数 maximum を 0 で初期化し、ループ用の一時変数 i も 0 で初期化します。
• unordered_map 型の変数 un_map を作成します。
• i が size 未満である間、while ループを繰り返します。
• ループ内では最初に len を 0 にセットし、un_map.find(arr[i]-1) != un_map.end() かつ len < un_map[arr[i]-1] が成り立てば、len を un_map[arr[i]-1] に更新します。
• 続いて un_map.find(arr[i]) != un_map.end() かつ len < un_map[arr[i]] なら、len を un_map[arr[i]] に更新します。
• さらに un_map.find(arr[i]+1) != un_map.end() かつ len < un_map[arr[i]+1] なら、len を un_map[arr[i]+1] に更新します。
• un_map[arr[i]] = len + 1 を設定します。
• maximum < un_map[arr[i]] であれば、maximum を un_map[arr[i]] の値で更新します。
• i の値をインクリメントします。
• ループを抜けたら maximum を返し、結果を出力します。

C++による実装例

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

// 最長部分列の長さを計算する関数
int maximum_adj(int arr[], int size){
    int maximum = 0, i = 0;
    unordered_map<int, int> un_map;
    while(i < size){
        int len = 0;
        if (un_map.find(arr[i]-1) != un_map.end() && len < un_map[arr[i]-1]){
            len = un_map[arr[i]-1];
        }
        if (un_map.find(arr[i]) != un_map.end() && len < un_map[arr[i]]){
            len = un_map[arr[i]];
        }
        if (un_map.find(arr[i]+1) != un_map.end() && len < un_map[arr[i]+1]){
            len = un_map[arr[i]+1];
        }
        un_map[arr[i]] = len + 1;
        if (maximum < un_map[arr[i]]){
            maximum = un_map[arr[i]];
        }
        i++;
    }
    return maximum;
}
int main(){
    int arr[] = {2, 3, 1, 7, 5, 6, 7, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"隣接要素の差が0または1となる最長部分列の長さ: "<< maximum_adj(arr, size);
    return 0;
}

出力

隣接要素の差が0または1となる最長部分列の長さ: 4

コードのポイント

• find() による存在チェック: operator[] で存在しないキーにアクセスすると、そのキーが値 0 で自動的に登録されてしまいます。そのため、必ず find() でキーの存在を先に確認してからアクセスしています。
• ±1 の範囲のみを確認: 「差が0または1」という条件は、「同じ値」「1大きい値」「1小さい値」の3パターンをチェックすれば十分であることを意味します。
• 動的計画法との類似性: 「その値で終わる最長部分列の長さ」を順次記録していく方式は、DP(動的計画法)の考え方をハッシュマップで実現したものと言えます。

計算量

• 時間計算量: O(n) — 配列を一度だけ走査し、ハッシュマップへの検索・挿入は平均 O(1) で行えます。
• 空間計算量: O(n) — 最悪の場合、配列内のすべての異なる値をマップに格納する必要があります。

まとめ

隣接要素の差が0または1となる最長部分列の問題は、unordered_map を使って「値ごとに最長長さを記録しながら ±1 の候補を参照する」ことで、O(n) の線形時間で効率的に解くことができます。部分列の全組み合わせを調べる必要がないため、大きな配列に対しても高速に動作するのが大きな魅力です。