Maximum Sum

Easy

0/40

Average time to solve is 20m

Contributed by

15 upvotes

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.

Detailed explanation ( Input/output format, Notes, Images )

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 :

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 :

Sample Output 2 :

7
52

Hint 1

Think about some special rearrangement greedily.

Approaches (1)

Approach 1

Optimal Approach

Approach :

We need to find a way to rearrange it such that it maximises the sum value.
The maximum values must be multiplied by the maximum number in order to perform optimal scaling.
So, we sort the array ‘A’ in ascending order.
We return the sum value for this rearrangement.

Algorithm :

Initialise a variable ‘ans’ as ‘0’ and ‘M=10^9+7’.
Sort the array ‘A’ in ascending order.
Run a loop from ‘i=0’ to ‘i=N-1’.
- Initialise a long variable ‘curr’ as ‘A[i]*i’ .
- Perform modulo on ‘curr’ = ‘curr%M’.
- Increment ‘ans’ by ‘curr’ and perform ‘ans%M’.
Return ‘ans’ as the final result.

Time Complexity

O(N*log(N)) , where ‘N’ is the size of array ‘A’.

We are sorting the array ‘A’, so the overall time complexity is O(N*log(N)).

Space Complexity

O(1)

Constant extra space is required. Hence, the overall Space Complexity is O(1).

(100% EXP penalty)

Maximum Sum

Console