Tối đa hóa tổng arr[i]*i bằng cách sắp xếp lại mảng trong C++

Đề bài

Cho mảng N số nguyên. Cho phép sắp xếp lại. Tìm max của Σ arr[i] * i (i = 0..n-1).

Ví dụ: {4,1,6,2} → sắp xếp {1,2,4,6} → 1*0 + 2*1 + 4*2 + 6*3 = 28.

Chứng minh

Theo bất đẳng thức sắp xếp (Rearrangement Inequality), tổng tích lớn nhất khi hai dãy cùng chiều biến thiên (cùng tăng hoặc cùng giảm). Vì i tăng dần (0,1,2...), nên arr[i] cũng nên tăng dần.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

int getMaxSum(int* arr, int n) {
    sort(arr, arr + n); // tăng dần
    int sum = 0;
    for (int i = 0; i < n; ++i)
        sum += arr[i] * i;
    return sum;
}

int main() {
    int arr[] = {4, 1, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Tong lon nhat = " << getMaxSum(arr, n) << endl;
    return 0;
}

Kết quả

Tong lon nhat = 28