C++で解く2つのソート済み配列の最大合計パス問題

問題概要

共通の要素を含みうる2つのソート済み配列が与えられます。このとき、どちらか一方の配列の先頭から出発し、2つの配列のいずれかの末尾に到達するまでの「最大合計パス」の和を求めてください。ただし、ある配列からもう一方の配列へ移動できるのは共通要素の位置のみです。なお、共通要素が同じインデックスに存在する必要はない点に注意してください。

期待される計算量は O(m+n) です。ここで m は arr1[] の要素数、n は arr2[] の要素数を表します。

具体例

入力:
arr1[] = {2, 3, 7, 10, 12}
arr2[] = {1, 5, 7, 8}

出力: 35
(1 + 5 + 7 + 10 + 12) = 35

• まず arr2 の最初の要素「1」からスタートし、「5」へ、さらに「7」へと進みます。

• 「7」は両配列の共通要素なので、ここで arr1 へ切り替え、「10」と「12」をたどります。

アルゴリズム

• マージソートのマージ処理に似たアプローチを用います。両方の配列について、共通点と共通点の間にある要素の合計をそれぞれ計算します。共通点を見つけるたびに2つの合計値を比較し、大きい方を結果に加算します。

• 結果を格納する変数 result を 0 で初期化します。同時に sum1 と sum2 も 0 で初期化します。sum1 と sum2 は、それぞれ arr1[] と arr2[] の要素の部分和を保持するためのもので、これらは「2つの共通点の間」の範囲の合計を表します。

• ループで両方の配列の要素を走査しながら、arr1[] と arr2[] の現在の要素を比較します。

  • arr1[] の現在の要素が arr2[] の現在の要素より小さい場合は sum1 を更新し、逆に arr2[] の方が小さい場合は sum2 を更新します。

  • 両者の現在の要素が等しい（共通要素）場合は、sum1 と sum2 の大きい方を結果に加算します。さらに、共通要素そのものも結果に加算したうえで、sum1 と sum2 をリセットします。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
int max(int x, int y){
    return (x > y)? x : y;
}
int maxPathSum(int *arr1, int *arr2, int m, int n){
    int i = 0, j = 0;
    int result = 0, sum1 = 0, sum2 = 0;
    while (i < m && j < n) {
        if (arr1[i] < arr2[j]) {
            sum1 += arr1[i++];
        } else if (arr1[i] > arr2[j]) {
            sum2 += arr2[j++];
        } else {
            result += max(sum1, sum2);
            sum1 = 0, sum2 = 0;
            while (i < m && j < n && arr1[i] == arr2[j]) {
                result = result + arr1[i++];
                j++;
            }
        }
    }
    while (i < m) {
        sum1 += arr1[i++];
    }
    while (j < n) {
        sum2 += arr2[j++];
    }
    result += max(sum1, sum2);
    return result;
}
int main(){
    int arr1[] = {2, 3, 7, 10, 12};
    int arr2[] = {1, 5, 7, 8};
    int m = sizeof(arr1)/sizeof(arr1[0]);
    int n = sizeof(arr2)/sizeof(arr2[0]);
    cout << "Maximum sum path = " << maxPathSum(arr1, arr2, m, n) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Maximum sum path = 35