C++の2つの配列の最大合計パス

問題の説明

2つのソートされた配列が与えられた場合、そのような配列にはいくつかの共通の要素が含まれる可能性があります。任意の配列の先頭から2つの配列のいずれかの末尾まで到達する最大合計パスの合計を見つけます。共通の要素でのみ、ある配列から別の配列に切り替えることができます。共通の要素が同じインデックスにある必要はないことに注意してください。

予想される時間計算量はO（m + n）です。ここで、mはarr1 []の要素数、nはarrs2 []

例

If given input is then output is 35
arr1[] = {2, 3, 7, 10, 12}
ar2[] = {1, 5, 7, 8}
(1 + 5 + 7 + 10 + 12) = 35

• 1. arr2の最初の要素である1から開始し、次に5に移動し、次に7に移動します。

• 7からar1（7が一般的）に切り替え、10と12をトラバースします。

アルゴリズム

• アイデアは、マージソートのマージプロセスに似た何かをすることです。両方の配列のすべての共通点間の要素の合計を計算する必要があります。共通点がある場合は常に、2つの合計を比較し、結果に最大2つを加算します。

• 結果を0として初期化します。また、2つの変数sum1とsum2を0として初期化します。ここで、sum1とsum2は、要素の合計をそれぞれarr1[]とarr2[]に格納するために使用されます。これらの合計は、2つの共通点の間にあります

• 次に、ループを実行して、両方の配列の要素をトラバースします。トラバース中に、arr1[]とarr2[]

  の現在の要素を比較します。

  • arr1[]の現在の要素がarr2[]の現在の要素よりも小さい場合は、sum1を更新します。そうでない場合は、arr2 []の現在の要素が小さい場合は、sumを更新します

  • arr1[]とarr2[]の現在の要素が同じである場合は、sum1とsum2の最大値を取得し、それを結果に追加します。また、結果に共通の要素を追加します

例

#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