C++で2つの配列から順番に要素を選択して最大合計を求める方法

この問題では、2つの配列 arr1[] と arr2[]、および2つの整数 N と M が与えられます。

N は arr1 から選択できる要素の最大数、M は arr2 から選択できる要素の最大数を表します。

各インデックス i において、arr1[i] と arr2[i] のどちらか一方の要素を選び、合計が最大になるようにします。ただし、arr1 からは最大 N 個、arr2 からは最大 M 個までしか選択できないという制約があります。

本記事では、C++ を使って2つの配列から順番に要素を選択し、最大合計を求めるプログラムの作成方法を解説します。

入力例と出力例

入力

arr1[] = {5, 1, 6, 2, 8, 9}
arr2[] = {8, 4, 7, 9, 1, 3}
N = 3, M = 2

出力

28

解説

各インデックスで選択する要素は以下の通りです。
i = 0 : arr1[0] = 5, arr2[0] = 8 → 8 を選択（arr2）
i = 1 : arr1[1] = 1, arr2[1] = 4 → 4 を選択（arr2）
i = 2 : arr1[2] = 6, arr2[2] = 7 → 6 を選択（arr1）
i = 3 : arr1[3] = 2, arr2[3] = 9 → 9 の代わりに 2 を選択（arr1）
i = 4 : arr1[4] = 8, arr2[4] = 1 → 8 を選択（arr1）

maxSum = 8 + 4 + 6 + 2 + 8 = 28

この例では、arr2 からは2個（M の上限）、arr1 からは3個（N の上限）選択しており、合計 28 が最大値となります。

解決アプローチ

この問題を解く基本的な考え方は貪欲法（グリーディ法）です。各インデックスにおいて、残り選択可能回数の制約内で、より大きい方の要素を選んでいきます。具体的には、次のように判断します。

• arr1[i] の方が大きく、かつ arr1 からの選択回数が残っている場合は arr1[i] を選ぶ。
• arr2[i] の方が大きく、かつ arr2 からの選択回数が残っている場合は arr2[i] を選ぶ。
• 片方の上限に達している場合は、もう片方の配列から選ぶ。
• 両方の上限に達した時点で処理を終了し、合計を返す。

アルゴリズム

初期化：

maxSum = 0

ステップ1：

for i → 0 to n-1

ステップ1.1：

if arr1[i] > arr2[i] かつ N > 0 → maxSum += arr1[i]、N をデクリメント

ステップ1.2：

else if arr1[i] <= arr2[i] かつ M > 0 → maxSum += arr2[i]、M をデクリメント

ステップ1.3：

else if M > 0 → maxSum += arr2[i]、M をデクリメント

ステップ1.4：

else if N > 0 → maxSum += arr1[i]、N をデクリメント

ステップ2：

それ以外の場合はループを抜けて maxSum を返す

C++実装例

以下は、この解法の動作を示すサンプルプログラムです。

#include <iostream>
using namespace std;

int calcMaxSumFromArrays(int arr1[], int arr2[], int N, int M, int size1, int size2) {
    int maxSum = 0;
    for(int i = 0; i < size1; i++){
        if(arr1[i] > arr2[i] && N > 0){
            maxSum += arr1[i];
            N--;
        }
        else if(arr1[i] <= arr2[i] && M > 0){
            maxSum += arr2[i];
            M--;
        }
        else if(M > 0){
            maxSum += arr2[i];
            M--;
        }
        else if(N > 0){
            maxSum += arr1[i];
            N--;
        }
        else
            return maxSum;
    }
    return maxSum;
}

int main() {
    int arr1[] = {5, 1, 6, 2, 8, 9};
    int arr2[] = {8, 4, 7, 9, 1, 3};
    int N = 3, M = 2;
    int size1 = sizeof(arr1)/sizeof(arr1[0]);
    int size2 = sizeof(arr2)/sizeof(arr2[0]);
    cout << "2つの配列から順番に要素を選択した場合の最大合計は "
         << calcMaxSumFromArrays(arr1, arr2, N, M, size1, size2);
    return 0;
}

出力

2つの配列から順番に要素を選択した場合の最大合計は 28

計算量の分析

• 時間計算量： O(n) ― 配列を一度だけ走査すればよいため、要素数 n に対して線形時間で処理できます。
• 空間計算量： O(1) ― カウンタと合計値を保持する変数のみを使用するため、追加のメモリは不要です。

まとめ

このように、各インデックスで大きい方の要素を優先的に選びつつ、選択回数の上限をカウンタで管理する貪欲なアプローチにより、効率的に最大合計を求めることができます。シンプルな条件分岐だけで実装できるため、配列操作と制約付き最適化の基礎を学ぶのに適した問題です。