সমস্যা বিবরণ
N সংখ্যক ইন্টিজারের একটি অ্যারে দেওয়া আছে। আপনাকে অ্যারে উপাদানগুলোর পুনর্বিন্যাস করার অনুমতি আছে। কাজ হল Σarr[i]*i-এর সর্বোচ্চ মান বের করা, যেখানে i = 0, 1, 2, ..., n-1।
যদি ইনপুট অ্যারে = {4, 1, 6, 2} হয় তবে সর্টেড ক্রমে উপাদান সাজিয়ে সর্বোচ্চ যোগফল ২৮ পাওয়া যায়:
{1, 2, 4, 6} = (1 * 0) + (2 * 1) + (4 * 2) + (6 * 3) = 28
অ্যালগরিদম
1. অ্যারেটি অ্যাসেন্ডিং ক্রমে সর্ট করুন। 2. অ্যারেটি ইটারেট করে প্রতিটি উপাদানকে i দিয়ে গুণ করুন যেখানে i = 0, 1, 2, ..., n-1। 3. যোগফল রিটার্ন করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int* arr, int n) {
sort(arr, arr + n);
int sum = 0;
for (int i = 0; i < n; ++i) {
sum = sum + arr[i] * i;
}
return sum;
}
int main() {
int arr[] = {4, 1, 6, 2};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
return 0;
}
আউটপুট
Maximum sum = 28
