সমস্যা বিবৃতি
দুটি সাজানো অ্যারে দেওয়া হয়েছে যেমন অ্যারেগুলিতে কিছু সাধারণ উপাদান থাকতে পারে। যেকোন অ্যারের শুরু থেকে শেষ পর্যন্ত দুটি অ্যারের যেকোনও প্রান্তে পৌঁছানোর জন্য সর্বাধিক সমষ্টি পথের যোগফল খুঁজুন। আমরা শুধুমাত্র সাধারণ উপাদানগুলিতে একটি অ্যারে থেকে অন্য অ্যারেতে স্যুইচ করতে পারি। মনে রাখবেন যে সাধারণ উপাদানগুলি একই সূচকে থাকতে হবে না।
প্রত্যাশিত সময়ের জটিলতা হল 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
