সমস্যা বিবরণ
দুটি সর্টেড অ্যারে দেওয়া আছে যাতে কিছু কমন এলিমেন্ট থাকতে পারে। যেকোনো একটি অ্যারের শুরু থেকে যেকোনো একটি অ্যারের শেষ পর্যন্ত ম্যাক্সিমাম সাম পাথ বের করতে হবে। শুধু কমন এলিমেন্টগুলোতে অ্যারে স্যুইচ করা যাবে। কমন এলিমেন্টগুলো একই ইনডেক্সে থাকতে হয় না।
সময় জটিলতা: O(m+n) যেখানে m, n হলো দুটি অ্যারের সাইজ।
উদাহরণ
ইনপুট: arr1[] = {2, 3, 7, 10, 12}, arr2[] = {1, 5, 7, 8}
আউটপুট: 35
পাথ: 1 + 5 + 7 + 10 + 12 = 35
- arr2-এর প্রথম এলিমেন্ট 1 থেকে শুরু, 5, 7।
- 7-তে (কমন) arr1-এ স্যুইচ করে 10, 12।
অ্যালগরिदম
- মার্জ সর্টের মার্জ প্রসেসের মতো। দুটি অ্যারেতে কমন পয়েন্টের মাঝপথে সাম ক্যালকুলেট। কমন পয়েন্টে দুটি সামের ম্যাক্সিমাম রেজাল্টে যোগ। কমন এলিমেন্টও যোগ।
- result=0, sum1=0, sum2=0। sum1, sum2 হচ্ছে দুটি কমন পয়েন্টের মাঝপথের সাম।
- while loop দিয়ে দুটি অ্যারে ট্রাভার্স। arr1[i] < arr2[j] হলে sum1+=arr1[i++]। arr1[i] > arr2[j] হলে sum2+=arr2[j++]। সমান হলে result += max(sum1,sum2) + arr1[i]; sum1=sum2=0; সব কমন এলিমেন্ট পাস করিয়ে i++, j++।
- বাকি এলিমেন্টগুলোর সাম যোগ করে result += max(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
