0

Maximum Sum

Difficulty: EASY
Contributed By
Avg. time to solve
20 min
Success Rate
80%

Problem Statement

Ninja likes rearranging arrays. This time he rearranges the array ‘A’ of size ‘N’ such that the sum of ‘A[i]*i’ over all indices is maximized.

Output the maximum sum achievable after rearranging the array ‘A’. Assume 0-based indexing. Since the answer can be large, output it modulo 10^9+7.

Example :
N = 3
A = [ 1, 2, 1 ]

Explanation : 

The rearrangements of array ‘A’ can be [ 1, 1, 2] , [ 1, 2, 1] and [ 2, 1, 1].
The sum for [ 1, 1, 2 ] is 0*1 + 1*1 + 2*2 = 5.
The sum for [ 1, 2, 1 ] is 0*1 + 1*2 + 2*1 = 4.
The sum for [ 2, 1, 1 ] is 0*2 + 1*1 + 2*1 = 3.
The maximum among these is 3.
Input Format :
The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’.

The next line contains ‘N’ integers representing the elements of array ‘A’ .
Output format :
For each test case, output an integer denoting the maximum sum.

Print the output of each test case in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
2 <= N <= 10^5
1 <= A[i] <= 10^5

Time Limit : 1 sec
Sample Input 1 :
2
2
1 1
3
1 2 3
Sample Output 1 :
1
8
Explanation Of Sample Input 1 :
For test case 1 we have, 

The sum of [ 1, 1 ] = 0*1 + 1*1 = 1.

There is no other rearrangement possible.

So, we output 1.

For test case 2 we have,

The maximum sum rearrangement is [ 1, 2, 3 ] with sum 0*1 + 1*2 + 2*3 = 8.

Hence, we output 8.   
Sample Input 2 :
2
2
7 2 
5
4 1 7 5 1 
Sample Output 2 :
7
52
Reset Code
Full screen
copy-code
Console