【C++】K個の連続する部分配列の最小値の中で最大値を最大化する方法

問題概要

配列 arr[] を K 個の連続する部分配列に分割し、それぞれの部分配列における最小値の中から最も大きい値を求めます。このとき、その最大値が取り得る値を最大化することが本問題の目的です。

入力

arr[] = {2,8,4,3,9,1,5}, K=3

出力

9

説明 − 作成できる3つの連続する部分配列は {2, 8, 4, 3}、{9}、{1, 5} です。

これらの配列の最小値はそれぞれ (2, 9, 1) となります。

この3つの値の中で最大なのは 9 です。

入力

arr[] = {8, 4, 1, 9, 11}, K=1

出力

11

プログラムで使用するアプローチ

• この問題は、K=1 の場合、K=2 の場合、そして K≧3 の場合という3つのケースに分けて考えることができます。

• ケース1 − K=1 の場合

  K=1 のとき、部分配列は元の配列そのものと等しいため、配列内の最小値がそのまま出力となります。

• ケース2 − K=2 の場合

  これはやや難しいケースです。配列は2つの部分にしか分割できないため、接頭辞（プレフィックス）の最小値と接尾辞（サフィックス）の最小値を格納する2つの配列を事前に作成しておく必要があります。その上で、配列の各分割位置 i に対して次のように処理を行います。

  MaxValue = max(MaxValue, max(i までの接頭辞の最小値, i+1 以降の接尾辞の最小値))

• ケース3 − K≧3 の場合

  K が3以上であれば、配列を3つ以上の部分に自由に分割できます。このとき、配列の最大値を持つ要素を単独の部分配列として切り出すことが可能です。残りの要素も前後の部分配列に振り分ければよいため、答えは必然的に配列全体の最大値となります。

例

#include <bits/stdc++.h>
using namespace std;
/* K個の部分配列の最小値のうちの最大値を求める関数 */
int Max(const int* arr, int size, int K){
    int Max = INT_MIN;
    int Min = INT_MAX;
    // 配列の最大値と最小値を求める
    for (int i = 0; i < size; i++){
        Min = min(Min, arr[i]);
        Max = max(Max, arr[i]);
    }
    // K=1 のときは最小値を返す
    if (K == 1){
        return Min;
    }
    // K>=3 のときは最大値を返す
    else if (K >= 3){
        return Max;
    }
    /* K=2 のときは接頭辞・接尾辞の最小値を作成する */
    else{
        // 接頭辞・接尾辞の最小値を格納する配列
        int Left[size], Right[size];
        Left[0] = arr[0];
        Right[size - 1] = arr[size - 1];
        // 接頭辞の最小値
        for (int i = 1; i < size; i++){
            Left[i] = min(Left[i - 1], arr[i]);
        }
        // 接尾辞の最小値
        for (int i = size - 2; i >= 0; i--){
            Right[i] = min(Right[i + 1], arr[i]);
        }
        int MaxValue = INT_MIN;
        // 最大可能値を求める
        for (int i = 0; i < size - 1; i++){
            MaxValue = max(MaxValue, max(Left[i], Right[i + 1]));
        }
        return MaxValue;
    }
}
int main(){
    int arr[] = {9,4,12,5,6,11};
    int size = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
    cout<<"K個の連続する部分配列の最小値のうち最大の値は: "<<Max(arr, size, K);
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます −

K個の連続する部分配列の最小値のうち最大の値は: 11

この結果は、配列 {9, 4, 12, 5, 6, 11} を {9, 4, 12, 5, 6} と {11} の2つの部分配列に分割したとき、各最小値 (4, 11) の中で最大の 11 が得られることを示しています。本アルゴリズムの計算量は O(n) であり、配列を数回走査するだけで答えを求められる効率的な手法です。