C++でK個の要素を削除した後の配列の中央要素の最大値を求める方法

はじめに

この記事では、配列からちょうどK個の要素を削除したときに、残った配列の中央要素として実現できる最大値を求めるC++プログラムを解説します。

サイズNの整数配列と整数Kが与えられます。どのK個を削除するかを工夫して、削除後の配列の中央要素をできるだけ大きな値にすることが課題です。

解き方の考え方

K個の要素を削除すると、残りの配列のサイズは N − K になります。このとき中央要素の位置（1始まり）は (N + 1 − K) / 2 で求められます。

ここで重要なのは、「先頭側から何個・末尾側から何個削除するか」を自由に選べるという点です。先頭から j 個、末尾から K − j 個を削除するように決めれば、削除後の中央要素は元の配列の次の範囲に含まれる要素のいずれかになります。

• 開始インデックス：low = (N + 1 − K) / 2
• 終了インデックス：high = low + K

つまり、この範囲にある要素の最大値を調べるだけで答えが求まります。すべての削除パターンを試す必要がないため、非常に効率的です。

C++による実装例

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

// 中央要素の最大値を計算する関数
int maximum_middle_value(int n, int k, int arr[]) {
    int ans = -1;
    int low = (n + 1 - k) / 2;
    int high = (n + 1 - k) / 2 + k;
    // 削除後の中央要素となり得る範囲から最大値を探す
    for (int i = low; i <= high; i++) {
        ans = max(ans, arr[i - 1]);
    }
    return ans;
}

int main() {
    int n = 5, k = 2;
    int arr[] = { 9, 5, 3, 7, 10 };
    cout << maximum_middle_value(n, k, arr) << endl;

    n = 9;
    k = 3;
    int arr1[] = { 2, 4, 3, 9, 5, 8, 7, 6, 10 };
    cout << maximum_middle_value(n, k, arr1) << endl;

    return 0;
}

コードの解説

maximum_middle_value 関数では、まず削除後の配列において中央要素が取り得る範囲を low と high として求めます。その後、for文でこの範囲を走査し、max 関数を使って範囲内の最大値を変数 ans に記録していきます。

実行結果

7
9

それぞれの動作を確認してみましょう。

• 例1：{ 9, 5, 3, 7, 10 } から K=2 個削除する場合、low=2、high=4 となるため候補は 5, 3, 7 であり、最大値の 7 が出力されます。
• 例2：{ 2, 4, 3, 9, 5, 8, 7, 6, 10 } から K=3 個削除する場合、low=3、high=6 となるため候補は 3, 9, 5, 8 であり、最大値の 9 が出力されます。

計算量

• 時間計算量：O(K)（low から high までの K+1 個の要素を走査）
• 空間計算量：O(1)（追加のメモリは不要）

まとめ

削除後の中央要素の位置に着目すると、答えとなり得るのは元の配列のごく一部の範囲だけであることが分かります。この性質を利用すれば、削除パターンを全探索することなく、線形時間で中央要素の最大値を効率よく求められます。