C++ में arr[i]*i के योग को अधिकतम करना

समस्या कथन

N पूर्णांकों का एक ऐरे दिया गया है। आपको ऐरे के तत्वों को पुनर्व्यवस्थित करने की अनुमति है। कार्य Σarr[i]*i का अधिकतम मान ढूंढना है, जहां i = 0, 1, 2, .. n-1।

यदि इनपुट ऐरे = {4, 1, 6, 2} तो अधिकतम योग 28 होगा यदि हम तत्वों को सॉर्टेड क्रम में पुनर्व्यवस्थित करें:

{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