C++で連続する同じ要素がK個を超えないように、合計が最大となるM個の要素を選択する方法

問題の概要

この問題では、配列 arr[] と2つの整数 M および K が与えられます。与えられた配列の要素を使って新しい配列を作成することが求められます。新しい配列のサイズは M であり、かつサイズが K より大きい任意の部分配列には、すべて同じ要素が含まれていてはいけません。そして、作成した配列の要素の合計として可能な最大値を出力します。

入力例

入力 − arr[] = {1, 2, 4, 5, 7 }, M = 5, K = 2

説明 − 条件を満たす配列は {7, 7, 5, 7, 7} となります。この配列では、サイズが2より大きい部分配列にすべて同じ要素が並ぶことはありません。

解決策のアプローチ

この問題を解くための基本的な考え方は、配列の中で最も大きな値（最大値）を使って配列を構成することです。しかし、同じ要素を K 回より多く連続して使用することはできないため、最大値を K 回使った後は、配列内で2番目に大きい値を使用する必要があります。

具体的には、最大値を K 個並べるごとに、2番目に大きい値を1つ挿入し、長さ M の配列を作成します。このとき、2番目に大きい値の出現回数は m / (k + 1) 回となり、残りの (m - max2count) 個は最大値で埋められます。したがって、最終的な答えは次の式で求められます。

合計 = max2count × max2 + (m − max2count) × max1

この手法により、配列を一度走査して最大値と2番目に大きい値を見つけるだけでよく、時間計算量は O(n)、空間計算量は O(1) という非常に効率的な解法になります。

実装例

上記の解法を実装したC++プログラムは以下の通りです。

#include <iostream>
using namespace std;
long int arraySum(int arr[], int n, int m, int k){
    int max1 = arr[0], max2 = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max1) {
            max2 = max1;
            max1 = arr[i];
        }
        else if (arr[i] > max2)
            max2 = arr[i];
    }
    int max2count = m / (k + 1);
    long int sum = max2count * max2 + (m - max2count) * max1;
    return sum;
}
int main() {
    int arr[] = { 1, 3, 6, 7, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 9, k = 2;
    cout<<"The maximum sum of array created from the given array such that no subarray of size greater than "<<k<<" will have same elements is ";
    cout<<arraySum(arr, n, m, k);
    return 0;
}

出力

The maximum sum of array created from the given array such that no subarray of size greater than 2 will have same elements is 60

コードの解説

まず、関数 arraySum 内でループを使って配列を一度だけ走査し、最大値 max1 と2番目に大きい値 max2 を求めています。次に、max2count = m / (k + 1) によって、2番目に大きい値を挿入すべき回数を計算します。これは、最大値を K 個連続で並べたブロックごとに1つの区切りが必要だからです。最後に、2番目に大きい値の合計と最大値の合計を足し合わせた結果を返しています。

サンプル入力の場合、arr[] = {1, 3, 6, 7, 4, 5}、M = 9、K = 2 であるため、最大値は7、2番目に大きい値は6となります。max2count = 9 / 3 = 3 なので、合計は 3 × 6 + 6 × 7 = 18 + 42 = 60 となり、出力結果と一致します。