Maximum Sum Path in Two Arrays - หาเส้นทางผลรวมสูงสุดระหว่างสองอาร์เรย์ใน C++

ปัญหา

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

ตัวอย่าง

arr1[] = {2, 3, 7, 10, 12}
arr2[] = {1, 5, 7, 8}
Output: 35 (1+5+7+10+12)

อัลกอริทึม (Merge-like Process)

1. i=0, j=0, result=0, sum1=0, sum2=0
2. while i
3. ถ้า arr1[i] < arr2[j]: sum1 += arr1[i++]
4. ถ้า arr1[i] > arr2[j]: sum2 += arr2[j++]
5. ถ้าเท่ากัน (ค่าร่วม):
   • result += max(sum1, sum2)
   • sum1=0, sum2=0
   • while ค่าร่วมต่อเนื่อง: result += arr1[i++], j++
6. เก็บผลรวมที่เหลือ: result += max(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 += 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