143. Maximize Sum of arr[i] * i After Rearranging

Given an array of n integers, rearrange its elements to maximize the sum of arr[i] * i over all 0-indexed positions i. Print that maximum sum.

Input: The first line contains an integer n. The second line contains n space-separated integers, the array elements. Output: Print a single integer - the maximum possible sum of arr[i] * i after rearranging.

1 <= n <= 10^5

This is a rearrangement-inequality problem - a well-known mathematical result stating that the sum of products is maximized when both sequences are sorted in the SAME order, and minimized when sorted in OPPOSITE orders.

Rearrange an array to maximize the sum of each element multiplied by its (0-indexed) position. Brute force: Try every possible permutation of the array and compute the sum for each - this is factorial time, impractical for large n, when a simple ascending sort is provably optimal. Optimised: Since larger indices act as bigger 'multipliers', an exchange argument shows that placing larger values at larger indices always beats the reverse (swapping any out-of-order pair to match ascending order never decreases the total) - a single ascending sort achieves the maximum directly.

Conceptually generate every possible arrangement of the array and compute the sum of arr[i]*i for each one, keeping the best result. This is guaranteed correct since it literally checks every possibility, but the number of arrangements grows factorially, making it usable only as a way to reason about correctness rather than as a practical algorithm. Time: O(n! * n) Space: O(n)

By an exchange argument, swapping two elements so that the smaller value sits at the smaller index and the larger value sits at the larger index never decreases the sum arr[i]*i, so the optimal arrangement is simply the array sorted ascending. Rearranging the array into ascending order using a simple selection sort (repeatedly finding the minimum remaining element and swapping it into place) achieves this without needing a full comparison-sort implementation, though it does more comparisons than necessary. Time: O(n^2) Space: O(1)

Sort the array ascending using an efficient comparison sort (merge sort / quicksort / the standard library sort), then compute sum(arr[i]*i) directly in one linear pass over the sorted result. This relies on the same rearrangement-inequality proof as the selection-sort version (ascending values paired with ascending indices maximizes the sum) but reaches the sorted order in log-linear time instead of quadratic time, which matters once n approaches 10^5. Time: O(n log n) Space: O(n)

1. Sort the array in ASCENDING order. 2. Since larger index positions contribute MORE weight (multiplying by a bigger number), pairing the SMALLEST values with the smallest indices and the LARGEST values with the largest indices maximizes the total. 3. Compute the sum of value times its new (sorted) index directly.

Time: O(n log n), dominated by the sort. Space: O(1) extra space beyond the sort itself.

n = 1 (the sum is always 0 regardless of arrangement), duplicate values in the array, and n at its maximum of 10^5 to confirm the sort-based approach runs efficiently.

Be ready to contrast this with a similar-looking MINIMIZATION variant (which would instead pair the LARGEST values with the SMALLEST indices) - the direction of the sort flips entirely depending on whether you're maximizing or minimizing.