เส้นทางรวมสูงสุดในสองอาร์เรย์ใน C++

คำชี้แจงปัญหา

เมื่อได้รับอาร์เรย์ที่จัดเรียงสองชุด อาร์เรย์ดังกล่าวอาจมีองค์ประกอบทั่วไปบางอย่าง ค้นหาผลรวมของเส้นทางผลรวมสูงสุดที่จะเข้าถึงจากจุดเริ่มต้นของอาร์เรย์ใดๆ ไปจนถึงจุดสิ้นสุดของอาร์เรย์ใดๆ ในสองอาร์เรย์ เราสามารถสลับจากอาร์เรย์หนึ่งไปยังอีกอาร์เรย์หนึ่งได้เฉพาะที่องค์ประกอบทั่วไปเท่านั้น โปรดทราบว่าองค์ประกอบทั่วไปไม่จำเป็นต้องอยู่ที่ดัชนีเดียวกัน

ความซับซ้อนของเวลาที่คาดหวังคือ O(m+n) โดยที่ m คือจำนวนองค์ประกอบใน arr1[] และ n คือจำนวนองค์ประกอบใน arr2[]

ตัวอย่าง

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

อัลกอริทึม

• แนวคิดคือการทำบางสิ่งที่คล้ายกับกระบวนการผสานของการเรียงลำดับการผสาน เราจำเป็นต้องคำนวณผลรวมขององค์ประกอบระหว่างจุดร่วมทั้งหมดสำหรับทั้งสองอาร์เรย์ เมื่อใดก็ตามที่เราเห็นจุดร่วม เราจะเปรียบเทียบผลรวมทั้งสองและเพิ่มค่าสูงสุดของสองเข้ากับผลลัพธ์

• เริ่มต้นผลลัพธ์เป็น 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