Maximum Sum

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in companies
OptumAmazonAmazon

Problem statement

You are given an array ‘arr’ consisting of ‘N’ integers. Your task is to maximize the value of 0 * arr[0] + 1 * arr[1] + 2 * arr[2] … (N - 1) * arr[N - 1] . You can rotate the array as many times as you wish.

For Example: 
For the given arr[ ] = { 1, 2, 3, 1} 
After 0 rotation arr[ ] = { 1, 2, 3, 1} the sum is = (0 *1 + 1 * 2 + 2 * 3 + 3 * 1) = 11.
After 1 rotation  arr[ ] = { 1, 1, 2, 3} the sum is = (0 *1 + 1 * 1 + 2 * 2 + 3 * 3) = 14.
After 2 rotation arr[ ] = { 3, 1, 1, 2} the sum is = (0 *3 + 1 * 1 + 2 * 1 + 3 * 2) = 9.
After 3 rotation arr[ ] = { 2, 3, 1, 1} the sum is = (0 *2 + 1 * 3 + 2 * 1 + 3 * 1) = 8.
So the maximum sum is 14 when arr[ ] = { 1, 1, 2, 3}.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. Then each test case follows.

The first line of each test case contains the Integer ‘N’ denoting the number of elements in the array.

The second and the last line of each test case contains ‘N’ single space-separated integers representing the elements of the array.
Output Format: 
For each test case, print an integer representing the maximum value of 0 * arr[0] + 1 * arr[1] + 2 * arr[2] … (N - 1) * arr[N - 1].

The output of each test case will be printed on a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 5 * 10 ^ 6
-10 ^ 5 <= arr[i] <= 10 ^ 5

Time Limit: 1 sec.
Sample Input 1:
2
4
1 2 3 1 
5
1 3 10 -2 0
Sample Output 1:
14
51
Explanation of Sample Input 1:
In the first test case, for the given arr[  ] = { 1, 2, 3, 1} 
After 0 rotation arr[ ] = { 1, 2, 3, 1} the sum is = (0 * 1 + 1 * 2 + 2 * 3 + 3 * 1) = 11.
After 1 rotation  arr[ ] = { 1, 1, 2, 3} the sum is = (0 * 1 + 1 * 1 + 2 * 2 + 3 * 3) = 14.
After 2 rotation arr[ ] = { 3, 1, 1, 2} the sum is = (0 * 3 + 1 * 1 + 2 * 1 + 3 * 2) = 9.
After 3 rotation arr[ ] = { 2, 3, 1, 1} the sum is = (0 * 2 + 1 * 3 + 2 * 1 + 3 * 1) = 8.
So the maximum sum is 14 when arr[ ] = { 1, 1, 2, 3}.

In the second test case, for the given arr[  ] = { 1, 3, 10, -2, 0} 
After 0 rotation arr[ ] ={ 1, 3, 10, -2, 0}  the sum is = (0 *1+1* 3 +2 *10 +3 *-2 + 4 * 0) = 17.
After 1 rotation arr[ ] ={ 0, 1, 3, 10, -2}  the sum is = (0 *0+1* 1 +2 *3 +3 *10 + 4 * -2) = 29.
After 2 rotation arr[ ] ={ -2, 0, 1, 3, 10}  the sum is = (0 *-2+1* 0 +2 *1 +3 *3 + 4 * 10) = 51.
After 3 rotation arr[ ] ={ 10, -2, 0, 1, 3}  the sum is = (0 *10+1* -2 +2 *0 +3 *1 + 4 * 3) = 13.
After 4 rotation arr[ ] ={ 3, 10, -2, 0, 1}  the sum is = (0 *3+1* 10 +2 *-2 +3 *0 + 4 * 1) = 10.
So the maximum sum is 51 when arr[ ] = { -2, 0, 1, 3, 10} .
Sample Input 2:
2
5
1 2 3 4 5
5
1 -2 3 -4 5
Sample Output 2:
40
14
Hint

Can you find out maximum value by trying out all possible rotations?

Approaches (2)
Brute Force

The idea is to try out all possible rotations and find the value 0 * arr[0] + 1 * arr[1] + 2 * arr[2] … (N - 1) * arr[N - 1]. We will iterate ‘i’ from 0 to N.

  1. The position of the element at index ‘j’ would become (i + j) % N.
  2. We will compute the sum, and the maximum value of all possible rotations would be our required answer.

 

Algorithm :

 

The steps are as follows:

  • Take a variable ‘res’ and initialize it to a minimum integer value.
  • Iterate ‘i’ from 0 to ‘N’, to consider all possible rotation
    • Take a variable ‘currSum’ and initialize it to 0.
    • Iterate ‘j’ from 0 to ‘N’ to compute the sum of all values as given in the question:
      • Take a variable ‘index’ and initialize it to (i + j) % N.
      • Increment ‘currSum’ by  j * arr[index].
    • Assign ‘res’ as the max of ‘res’ and ‘currSum’.
  • Return ‘res’.
Time Complexity

O(N ^ 2) where ‘N’ is the number of elements in the given array.

 

We will rotate the array ‘N’ times. We will calculate the value by iterating through the array that takes O(N) time for each rotation. Hence the overall time complexity is O(N * N ) = O(N ^ 2).

Space Complexity

O(1).

 

We are not using any extra space. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Maximum Sum
Full screen
Console