সমস্যা বিবরণ
একই আকারের দুটি অ্যারে দেওয়া থাকলে, প্রথম অ্যারের প্রতিটি এলিমেন্টকে দ্বিতীয় অ্যারের একটি এলিমেন্ট দিয়ে গুণ করে সর্বোচ্চ মোট সম বের করতে হবে। প্রতিটি এলিমেন্ট ঠিক একবার ব্যবহার করা হবে।
উপায়: উভয় অ্যারে সর্ট করুন এবং সমাবেশী ইন্ডেক্সগুলো গুণ করুন।
সমাধানের পদ্ধতি
- উভয় অ্যারে সর্ট করুন।
- সমাবেশী ইন্ডেক্সগুলোর গুণফল যোগ করুন।
- সর্বোচ্চ সম পাওয়া যাবে।
নোট: অ্যারে সাইজ হিসাবের কোডে বাগ আছে (sizeof পয়েন্টারে কাজ করে না), নিচে সংশোধন করা হয়েছে।
C++ কোড উদাহরণ (সংশোধিত)
#include <bits/stdc++.h>
using namespace std;
int maximumSOP(int a[], int b[], int n) {
int sop = 0;
sort(a, a + n);
sort(b, b + n);
for (int i = 0; i < n; i++) {
sop += a[i] * b[i];
}
return sop;
}
int main() {
int A[] = {1, 2, 3};
int B[] = {4, 5, 1};
int n = sizeof(A) / sizeof(A[0]);
cout << maximumSOP(A, B, n);
return 0;
}
আউটপুট
24
ব্যাখ্যা
সর্টেড A: [1,2,3], সর্টেড B: [1,4,5]
সম = 1×1 + 2×4 + 3×5 = 1 + 8 + 15 = 24
জটিলতা
- সময়: O(n log n)
- স্থান: O(1)
