Đường dẫn tổng tối đa trong hai mảng trong C ++

Tuyên bố vấn đề

Cho hai mảng được sắp xếp như vậy các mảng có thể có một số phần tử chung. Tìm tổng của đường dẫn tổng lớn nhất đạt được từ đầu của bất kỳ mảng nào đến cuối của bất kỳ trong hai mảng. Chúng ta có thể chuyển từ mảng này sang mảng khác chỉ tại các phần tử chung. Lưu ý rằng các phần tử chung không nhất thiết phải có cùng chỉ mục.

Độ phức tạp thời gian mong đợi là O (m + n) trong đó m là số phần tử trong arr1 [] và n là số phần tử trong arrs2 []

Ví dụ

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. Chúng tôi bắt đầu từ phần tử đầu tiên của arr2 là 1, sau đó chúng tôi chuyển sang 5, sau đó là 7.

• Từ 7, chúng tôi chuyển sang ar1 (7 là phổ biến) và chuyển qua 10 và 12.

Thuật toán

• Ý tưởng là làm một cái gì đó tương tự như quá trình hợp nhất của sắp xếp hợp nhất. Chúng ta cần tính tổng các phần tử giữa tất cả các điểm chung cho cả hai mảng. Bất cứ khi nào chúng tôi thấy một điểm chung, chúng tôi so sánh hai tổng và cộng tối đa hai vào kết quả.

• Khởi tạo kết quả là 0. Đồng thời khởi tạo hai biến sum1 và sum2 bằng 0. Ở đây sum1 và sum2 được sử dụng để lưu trữ tổng của phần tử trong arr1 [] và arr2 [] tương ứng. Các tổng này nằm giữa hai điểm chung

• Bây giờ chạy một vòng lặp để duyệt qua các phần tử của cả hai mảng. Trong khi duyệt so sánh các phần tử hiện tại của arr1 [] và arr2 []

  • Nếu phần tử hiện tại của arr1 [] nhỏ hơn phần tử hiện tại của arr2 [] thì hãy cập nhật sum1, ngược lại nếu phần tử hiện tại của arr2 [] nhỏ hơn thì hãy cập nhật sum

  • Nếu phần tử hiện tại của arr1 [] và arr2 [] giống nhau, thì lấy giá trị lớn nhất của sum1 và sum2 rồi thêm vào kết quả. Đồng thời thêm phần tử chung vào kết quả

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Maximum sum path = 35