C++에서 두 배열의 최대 합 경로

문제 설명

두 개의 정렬된 배열이 주어지면 이러한 배열에는 몇 가지 공통 요소가 있을 수 있습니다. 임의의 배열의 시작에서 두 배열의 끝까지 도달하는 최대 합 경로의 합을 찾으십시오. 공통 요소에서만 한 배열에서 다른 배열로 전환할 수 있습니다. 공통 요소가 동일한 색인에 있을 필요는 없습니다.

예상 시간 복잡도는 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를 더합니다.

• 결과를 0으로 초기화합니다. 또한 두 변수 sum1과 sum2를 0으로 초기화합니다. 여기서 sum1과 sum2는 각각 arr1[]과 arr2[]에 요소의 합을 저장하는 데 사용됩니다. 이 합계는 두 가지 공통점 사이에 있습니다.

• 이제 루프를 실행하여 두 배열의 요소를 탐색합니다. 순회하는 동안 arr1[] 및 arr2[]

  의 현재 요소를 비교합니다.

  • arr1[]의 현재 요소가 arr2[]의 현재 요소보다 작으면 sum1을 업데이트하고, arr2[]의 현재 요소가 더 작으면 합계를 업데이트합니다.

  • 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